Hypercube graph - Revision history

https://graph.subwiki.org/w/index.php?action=history&feed=atom&title=Hypercube_graph Hypercube graph - Revision history 2026-06-16T15:30:28Z Revision history for this page on the wiki MediaWiki 1.41.2 https://graph.subwiki.org/w/index.php?title=Hypercube_graph&diff=166&oldid=prev Vipul: /* Size measures */ 2012-05-29T16:19:23Z

<p><span dir="auto"><span class="autocomment">Size measures</span></span></p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="en"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 16:19, 29 May 2012</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l17">Line 17:</td> <td colspan="2" class="diff-lineno">Line 17:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>| [[size of vertex set]] || <math>2^n</math> || Each time we increment <math>n</math> by 1, the number of vertices doubles</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>| [[size of vertex set]] || <math>2^n</math> || Each time we increment <math>n</math> by 1, the number of vertices doubles</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>|-</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>|-</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>| [[size of edge set]] || <math>2^{n-1}<del style="font-weight: bold; text-decoration: none;">(2n - 3)</del></math> || By the definition of prism, if <math>a_n</math> denotes the number of edges in the <math>n</math>-hypercube, then <math>a_n = 2a_{n-1} + 2^{n-1}</math>. Further, <math>a_1 = 1</math>. We solve the recurrence relation and obtain the expression.</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>| [[size of edge set]] || <math><ins style="font-weight: bold; text-decoration: none;">n \cdot </ins>2^{n-1}</math> || By the definition of prism, if <math>a_n</math> denotes the number of edges in the <math>n</math>-hypercube, then <math>a_n = 2a_{n-1} + 2^{n-1}</math>. Further, <math>a_1 = 1</math>. We solve the recurrence relation and obtain the expression.</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>|}</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>|}</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td></tr> </table>

Vipul https://graph.subwiki.org/w/index.php?title=Hypercube_graph&diff=165&oldid=prev Vipul: /* Arithmetic functions */ 2012-05-29T16:18:30Z

<p><span dir="auto"><span class="autocomment">Arithmetic functions</span></span></p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="en"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 16:18, 29 May 2012</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l17">Line 17:</td> <td colspan="2" class="diff-lineno">Line 17:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>| [[size of vertex set]] || <math>2^n</math> || Each time we increment <math>n</math> by 1, the number of vertices doubles</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>| [[size of vertex set]] || <math>2^n</math> || Each time we increment <math>n</math> by 1, the number of vertices doubles</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>|-</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>|-</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>| [[size of edge set]] || <math>2^{n-1}(2n - <del style="font-weight: bold; text-decoration: none;">1</del>)</math> || By the definition of prism, if <math>a_n</math> denotes the number of edges in the <math>n</math>-hypercube, then <math>a_n = 2a_{n-1} + 2^{n-1}</math>. Further, <math>a_1 = 1</math>. We solve the recurrence relation and obtain the expression.</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>| [[size of edge set]] || <math>2^{n-1}(2n - <ins style="font-weight: bold; text-decoration: none;">3</ins>)</math> || By the definition of prism, if <math>a_n</math> denotes the number of edges in the <math>n</math>-hypercube, then <math>a_n = 2a_{n-1} + 2^{n-1}</math>. Further, <math>a_1 = 1</math>. We solve the recurrence relation and obtain the expression.</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>|}</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>|}</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td></tr> </table>

Vipul https://graph.subwiki.org/w/index.php?title=Hypercube_graph&diff=164&oldid=prev Vipul: Created page with "{{undirected graph family}} ==Definition== A <math>n</math>-dimensional '''hypercube graph''' is defined in the follwing equivalent ways: # It is the graph of the <math>n</..." 2012-05-29T16:15:42Z

<p>Created page with "{{undirected graph family}} ==Definition== A <math>n</math>-dimensional '''hypercube graph''' is defined in the follwing equivalent ways: # It is the graph of the <math>n</..."</p> <p><b>New page</b></p><div>{{undirected graph family}}<br /> <br /> ==Definition==<br /> <br /> A <math>n</math>-dimensional '''hypercube graph''' is defined in the follwing equivalent ways:<br /> <br /> # It is the graph of the <math>n</math>-dimensional hypercube, i.e., the graph whose vertices are the vertices of the <math>n</math>-dimensional hypercube and whose edges are the edges of the <math>n</math>-dimensional hypercube.<br /> # It is defined inductively as follows: for <math>n = 1</math>, it is the [[complete graph:K2]], and for <math>n \ge 2</math>, it is the prism of the <math>(n-1)</math>-dimensional hypercube.<br /> <br /> ==Arithmetic functions==<br /> <br /> ===Size measures===<br /> <br /> {| class="sortable" border="1"<br /> ! Function !! Value !! Explanation<br /> |-<br /> | [[size of vertex set]] || <math>2^n</math> || Each time we increment <math>n</math> by 1, the number of vertices doubles<br /> |-<br /> | [[size of edge set]] || <math>2^{n-1}(2n - 1)</math> || By the definition of prism, if <math>a_n</math> denotes the number of edges in the <math>n</math>-hypercube, then <math>a_n = 2a_{n-1} + 2^{n-1}</math>. Further, <math>a_1 = 1</math>. We solve the recurrence relation and obtain the expression.<br /> |}<br /> <br /> ===Numerical invariants associated with vertices===<br /> <br /> Since the graph is a [[vertex-transitive graph]], any numerical invariant associated to a vertex must be equal on all vertices of the graph. Below are listed some of these invariants:<br /> <br /> {| class="sortable" border="1"<br /> ! Function !! Value !! Explanation<br /> |-<br /> | [[degree of a vertex]] || <matH>n</math> || Each time we apply the prism construction, the degree goes up by 1.<br /> |-<br /> | [[eccentricity of a vertex]] || <math>n</math> || Each time we apply the prism construction, the eccentricity of every vertex goes up by 1.<br /> |}<br /> <br /> ===Other numerical invariants===<br /> <br /> {| class="sortable" border="1"<br /> ! Function !! Value !! Explanation<br /> |-<br /> | {{arithmetic function value|clique number|2}} || The graph is bipartite, hence triangle-free<br /> |-<br /> | [[independence number]] || <math>2^{n-1}</math> || Thinking geometrically in terms of the hypercube, the graph is bipartite, with the two parts defined by the parity of the sums of coordinates of vertices if we coordinatize the hypercube as <math>\{ 0,1 \}^n</math>. Both parts have sizes <math>2^{n-1}</math>.<br /> |-<br /> | {{arithmetic function value|chromatic number|2}} || Thinking geometrically in terms of the hypercube, the graph is bipartite, with the two parts defined by the parity of the sums of coordinates of vertices if we coordinatize the hypercube as <math>\{ 0,1 \}^n</math>.<br /> |-<br /> | [[radius of a graph]] || <math>n</math> || Due to vertex-transitivity, the radius equals the eccentricity of any vertex, which has been computed above.<br /> |-<br /> | [[diameter of a graph]] || <math>n</math> || Due to vertex-transitivity, the diameter equals the eccentricity of any vertex, which has been computed above.<br /> |-<br /> | {{arithmetic function value|girth of a graph|4}} (except the case <math>n = 1</math>, that has infinite girth) || The 2-hypercube is [[cycle graph:C4]]. All higher hypercubes contain this as a subgraph.<br /> |-<br /> | [[odd girth]] || infinite || Thinking geometrically in terms of the hypercube, the graph is bipartite, with the two parts defined by the parity of the sums of coordinates of vertices if we coordinatize the hypercube as <math>\{ 0,1 \}^n</math>.<br /> |-<br /> | {{arithmetic function value|even girth|4}} (except the case <math>n = 1</math>, that has infinite girth) || The 2-hypercube is [[cycle graph:C4]]. All higher hypercubes contain this as a subgraph.<br /> |}</div>

Vipul