Hypercube graph =============== {{Infobox graph | name = Hypercube graph | image = Hypercubestar.svg | image_size = 200px | image_caption = The hypercube graph Q_4 | vertices = 2^n | edges = 2^{n-1}n | automorphisms = n!2^n | chromatic_number = 2 | chromatic_index = | girth = 4 if n\ge 2 | diameter = n | spectrum = \{(n - 2 k)^{\binom{n}{k}}; k = 0, \ldots, n\} | properties = Symmetric Distance regular Unit distance Hamiltonian Bipartite Polytopal | notation = Q_n }} In graph theory, the hypercube graph Q_n is the edge graph of the n -dimensional hypercube, that is, it is the graph formed from the vertices and edges of the hypercube. For instance, the cube graph Q_3 is the graph formed by the 8 vertices and 12 edges of a three-dimensional cube. Q_n has 2^n vertices, 2^{n-1}n edges, and is a regular graph with n edges touching each vertex. The hypercube graph Q_n may also be constructed by creating a vertex for each subset of an n -element set, with two vertices adjacent when their subsets differ in a single element, or by creating a vertex for each n -digit binary number, with two vertices adjacent when their binary representations differ in a single digit. It is the n -fold Cartesian product of the two-vertex complete graph, and may be decomposed into two copies of Q_{n-1} connected to each other by a perfect matching.… {{Infobox graph | name = Hypercube graph | image = Hypercubestar.svg | image_size = 200px | image_caption = The hypercube graph Q_4 | vertices = 2^n | edges = 2^{n-1}n | automorphisms = n!2^n | chromatic_number = 2 | chromatic_index = | girth = 4 if n\ge 2 | diameter = n | spectrum = \{(n - 2 k)^{\binom{n}{k}}; k = 0, \ldots, n\} | properties = Symmetric Distance regular Unit distance Hamiltonian Bipartite Polytopal | notation = Q_n }} In graph theory, the hypercube graph Q_n is the edge graph of the n -dimensional hypercube, that is, it is the graph formed from the vertices and edges of the hypercube. For instance, the cube graph Q_3 is the graph formed by the 8 vertices and 12 edges of a three-dimensional cube. Q_n has 2^n vertices, 2^{n-1}n edges, and is a regular graph with n edges touching each vertex. The hypercube graph Q_n may also be constructed by creating a vertex for each subset of an n -element set, with two vertices adjacent when their subsets differ in a single element, or by creating a vertex for each n -digit binary number, with two vertices adjacent when their binary representations differ in a single digit. It is the n -fold Cartesian product of the two-vertex complete graph, and may be decomposed into two copies of Q_{n-1} connected to each other by a perfect matching. Hypercube graphs should not be confused with cubic graphs, which are graphs that have exactly three edges touching each vertex. The only hypercube graph Q_n that is a cubic graph is the cubical graph Q_3 . The above construction gives a recursive algorithm for constructing the adjacency matrix of a hypercube, A_n . Copying is done via the Kronecker product \otimes_K , so that the two copies of Q_{n-1} have an adjacency matrix \mathrm{1}_2\otimes_K A_{n-1} ,where 1_d is the d\times d identity matrix. Meanwhile the joining edges have an adjacency matrix A_{1} \otimes_K 1_{2^{n-1} } . The sum of these two terms gives a recursive function for the adjacency matrix of a hypercube: A_{n} = \begin{cases} 1_2\otimes_K A_{n-1}+A_1\otimes_K 1_{2^{n-1}} & \text{if } n>1\\ \begin{bmatrix} 0 & 1\\ 1 & 0 \end{bmatrix} &\text{if }n=1 \end{cases} Another construction of Q_n is the Cartesian product of n two-vertex complete graphs K_2 . More generally the Cartesian product of copies of a complete graph is called a Hamming graph; the hypercube graphs are examples of Hamming graphs. ===Bipartiteness=== Every hypercube graph is bipartite: it can be colored with only two colors. The two colors of this coloring may be found from the subset construction of hypercube graphs, by giving one color to the subsets that have an even number of elements and the other color to the subsets with an odd number of elements. has exactly 2^{2^n-n-1}\prod_{k=2}^n k^ spanning trees. has bandwidth exactly \sum_{i=0}^{n-1} \binom{i}{\lfloor i/2\rfloor} . has achromatic number proportional to \sqrt{n2^n} , but the constant of proportionality is not known precisely. has as the eigenvalues of its adjacency matrix the numbers \{-n,-n+2,-n+4,\dots,n-4,n-2,n\} and as the eigenvalues of its Laplacian matrix the numbers \{0,2,\dots,2n\} . The k th eigenvalue has multiplicity \binom{n}{k} in both cases. has isoperimetric number h(G)=1 . The family Q_n for all n>1 is a Lévy family of graphs. REFERENCES ---------- BIBLIOGRAPHY (BibTeX) -------------------- @article{ref0, title = {Hypercube graph}, url = {https://encyclopegia.org/a/hypercube-graph} } BIBLIOGRAPHY (RIS) ------------------- TY - JOUR TI - Hypercube graph UR - https://encyclopegia.org/a/hypercube-graph ER - CITE THIS ARTICLE ---------------- Cite this article: Hypercube graph Derived from: https://en.wikipedia.org/w/index.php?oldid=1366110735 Licence: CC BY-SA 4.0 Snapshot: enwiki-001366110735 Permalink: /a/hypercube-graph