Hypercube graph | |
---|---|

The hypercube graph Q_{4} | |

Vertices | 2^{n} |

Edges | 2^{n−1}n |

Diameter | n |

Girth | 4 if n ≥ 2 |

Automorphisms | n! 2^{n} |

Chromatic number | 2 |

Spectrum | |

Properties | Symmetric Distance regular Unit distance Hamiltonian Bipartite |

Notation | Q_{n} |

Table of graphs and parameters |

In graph theory, the **hypercube graph***Q _{n}* is the graph formed from the vertices and edges of an n-dimensional hypercube. For instance, the cubical graph

- Construction
- Examples
- Properties
- Bipartiteness
- Hamiltonicity
- Other properties
- Problems
- See also
- Notes
- References

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

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 hypercube graph *Q*_{n} may be constructed from the family of subsets of a set with n elements, by making a vertex for each possible subset and joining two vertices by an edge whenever the corresponding subsets differ in a single element. Equivalently, it may be constructed using 2^{n} vertices labeled with n-bit binary numbers and connecting two vertices by an edge whenever the Hamming distance of their labels is one. These two constructions are closely related: a binary number may be interpreted as a set (the set of positions where it has a 1 digit), and two such sets differ in a single element whenever the corresponding two binary numbers have Hamming distance one.

Alternatively, *Q*_{n} may be constructed from the disjoint union of two hypercubes *Q*_{n− 1}, by adding an edge from each vertex in one copy of *Q*_{n− 1} to the corresponding vertex in the other copy, as shown in the figure. The joining edges form a perfect matching.

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.

The graph *Q*_{0} consists of a single vertex, while *Q*_{1} is the complete graph on two vertices and *Q*_{2} is a cycle of length 4.

The graph *Q*_{3} is the 1-skeleton of a cube, a cubical graph, a planar graph with eight vertices and twelve edges.

The graph *Q*_{4} is the Levi graph of the Möbius configuration. It is also the knight's graph for a toroidal chessboard.^{ [1] }

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.

Every hypercube *Q*_{n} with *n* > 1 has a Hamiltonian cycle, a cycle that visits each vertex exactly once. Additionally, a Hamiltonian path exists between two vertices u and v if and only if they have different colors in a 2-coloring of the graph. Both facts are easy to prove using the principle of induction on the dimension of the hypercube, and the construction of the hypercube graph by joining two smaller hypercubes with a matching.

Hamiltonicity of the hypercube is tightly related to the theory of Gray codes. More precisely there is a bijective correspondence between the set of n-bit cyclic Gray codes and the set of Hamiltonian cycles in the hypercube *Q*_{n}.^{ [2] } An analogous property holds for acyclic *n*-bit Gray codes and Hamiltonian paths.

A lesser known fact is that every perfect matching in the hypercube extends to a Hamiltonian cycle.^{ [3] } The question whether every matching extends to a Hamiltonian cycle remains an open problem.^{ [4] }

The hypercube graph *Q*_{n} (for *n* > 1) :

- is the Hasse diagram of a finite Boolean algebra.
- is a median graph. Every median graph is an isometric subgraph of a hypercube, and can be formed as a retraction of a hypercube.
- has more than 2
^{2n-2}perfect matchings. (this is another consequence that follows easily from the inductive construction.) - is arc transitive and symmetric. The symmetries of hypercube graphs can be represented as signed permutations.
- contains all the cycles of length 4, 6, ..., 2
^{n}and is thus a bipancyclic graph. - can be drawn as a unit distance graph in the Euclidean plane by using the construction of the hypercube graph from subsets of a set of n elements, choosing a distinct unit vector for each set element, and placing the vertex corresponding to the set S at the sum of the vectors in S.
- is a n-vertex-connected graph, by Balinski's theorem
- is planar (can be drawn with no crossings) if and only if
*n*≤ 3. For larger values of n, the hypercube has genus (*n*− 4)2^{n− 3}+ 1.^{ [5] }^{ [6] } - has exactly spanning trees.
^{ [6] } - has bandwidth exactly .
^{ [7] } - has achromatic number proportional to , but the constant of proportionality is not known precisely.
^{ [8] } - has as the eigenvalues of its adjacency matrix the numbers (−
*n*, −*n*+ 2, −*n*+ 4, ... ,*n*− 4,*n*− 2,*n*) and as the eigenvalues of its Laplacian matrix the numbers (0, 2, ..., 2*n*). The kth eigenvalue has multiplicity in both cases. - has isoperimetric number
*h*(*G*) = 1.

The family *Q*_{n} for all *n* > 1 is a Lévy family of graphs

The problem of finding the longest path or cycle that is an induced subgraph of a given hypercube graph is known as the snake-in-the-box problem.

Szymanski's conjecture concerns the suitability of a hypercube as a network topology for communications. It states that, no matter how one chooses a permutation connecting each hypercube vertex to another vertex with which it should be connected, there is always a way to connect these pairs of vertices by paths that do not share any directed edge.^{ [9] }

Wikimedia Commons has media related to . Hypercube graphs |

- ↑ Watkins, John J. (2004),
*Across the Board: The Mathematics of Chessboard Problems*, Princeton University Press, p. 68, ISBN 978-0-691-15498-5 . - ↑ Mills, W. H. (1963), "Some complete cycles on the n-cube",
*Proceedings of the American Mathematical Society*, American Mathematical Society,**14**(4): 640–643, doi:10.2307/2034292, JSTOR 2034292 . - ↑ Fink, J. (2007), "Perfect matchings extend to Hamiltonian cycles in hypercubes",
*Journal of Combinatorial Theory, Series B*,**97**(6): 1074–1076, doi:10.1016/j.jctb.2007.02.007 . - ↑ Ruskey, F. and Savage, C. Matchings extend to Hamiltonian cycles in hypercubes on Open Problem Garden. 2007.
- ↑ Ringel, G. (1955), "Über drei kombinatorische Probleme am n-dimensionalen Wiirfel und Wiirfelgitter",
*Abh. Math. Sem. Univ. Hamburg*,**20**: 10–19, MR 0949280 - 1 2 Harary, Frank; Hayes, John P.; Wu, Horng-Jyh (1988), "A survey of the theory of hypercube graphs" (PDF),
*Computers & Mathematics with Applications*,**15**(4): 277–289, doi:10.1016/0898-1221(88)90213-1, MR 0949280 . - ↑ Optimal Numberings and Isoperimetric Problems on Graphs, L.H. Harper, Journal of Combinatorial Theory, 1, 385–393, doi : 10.1016/S0021-9800(66)80059-5
- ↑ Roichman, Y. (2000), "On the Achromatic Number of Hypercubes",
*Journal of Combinatorial Theory, Series B*,**79**(2): 177–182, doi:10.1006/jctb.2000.1955 . - ↑ Szymanski, Ted H. (1989), "On the Permutation Capability of a Circuit-Switched Hypercube",
*Proc. Internat. Conf. on Parallel Processing*,**1**, Silver Spring, MD: IEEE Computer Society Press, pp. 103–110.

In geometry, a scientific cuboid **cube** is a three-dimensional solid object bounded by six square faces, facets or sides, with three meeting at each vertex.

In geometry, a **hypercube** is an *n*-dimensional analogue of a square and a cube. It is a closed, compact, convex figure whose 1-skeleton consists of groups of opposite parallel line segments aligned in each of the space's dimensions, perpendicular to each other and of the same length. A unit hypercube's longest diagonal in *n* dimensions is equal to .

In the mathematical field of graph theory, the **Petersen graph** is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph is named after Julius Petersen, who in 1898 constructed it to be the smallest bridgeless cubic graph with no three-edge-coloring.

In the mathematical field of graph theory, a **bipartite graph** is a graph whose vertices can be divided into two disjoint and independent sets and such that every edge connects a vertex in to one in . Vertex sets and are usually called the *parts* of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles.

In graph theory, a branch of mathematics, the (binary) **cycle space** of an undirected graph is the set of its even-degree subgraphs.

This is a **glossary of graph theory terms**. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

In the mathematical field of graph theory, the **Desargues graph** is a distance-transitive cubic graph with 20 vertices and 30 edges. It is named after Girard Desargues, arises from several different combinatorial constructions, has a high level of symmetry, is the only known non-planar cubic partial cube, and has been applied in chemical databases.

In graph theory, the **Kneser graph***K*(*n*, *k*) is the graph whose vertices correspond to the k-element subsets of a set of n elements, and where two vertices are adjacent if and only if the two corresponding sets are disjoint. Kneser graphs are named after Martin Kneser, who first investigated them in 1955.

In the mathematical field of graph theory, the **Möbius–Kantor graph** is a symmetric bipartite cubic graph with 16 vertices and 24 edges named after August Ferdinand Möbius and Seligmann Kantor. It can be defined as the generalized Petersen graph *G*(8,3): that is, it is formed by the vertices of an octagon, connected to the vertices of an eight-point star in which each point of the star is connected to the points three steps away from it.

**Clique complexes**, **flag complexes**, and **conformal hypergraphs** are closely related mathematical objects in graph theory and geometric topology that each describe the cliques of an undirected graph.

In graph theory, a branch of mathematics, a **crown graph** on 2*n* vertices is an undirected graph with two sets of vertices {*u*_{1}, *u*_{2}, ..., *u*_{n}} and {*v*_{1}, *v*_{2}, ..., *v*_{n}} and with an edge from *u*_{i} to *v*_{j} whenever *i* ≠ *j*.

In the mathematical field of graph theory, the **odd graphs***O _{n}* are a family of symmetric graphs with high odd girth, defined from certain set systems. They include and generalize the Petersen graph.

In the mathematical field of graph theory, the **Clebsch graph** is either of two complementary graphs on 16 vertices, a 5-regular graph with 40 edges and a 10-regular graph with 80 edges. The 80-edge variant is the order-5 halved cube graph; it was called the Clebsch graph name by Seidel (1968) because of its relation to the configuration of 16 lines on the quartic surface discovered in 1868 by the German mathematician Alfred Clebsch. The 40-edge variant is the order-5 folded cube graph; it is also known as the **Greenwood–Gleason graph** after the work of Robert E. Greenwood and Andrew M. Gleason (1955), who used it to evaluate the Ramsey number *R*(3,3,3) = 17.

In graph theory, a branch of mathematics, a **Hamiltonian decomposition** of a given graph is a partition of the edges of the graph into Hamiltonian cycles. Hamiltonian decompositions have been studied both for undirected graphs and for directed graphs; in the undirected case, a Hamiltonian decomposition can also be described as a 2-factorization of the graph such that each factor is connected.

In graph theory, a **folded cube graph** is an undirected graph formed from a hypercube graph by adding to it a perfect matching that connects *opposite* pairs of hypercube vertices.

In graph theory, a **partial cube** is a graph that is isometric to a subgraph of a hypercube. In other words, a partial cube can be identified with a subgraph of a hypercube in such a way that the distance between any two vertices in the partial cube is the same as the distance between those vertices in the hypercube. Equivalently, a partial cube is a graph whose vertices can be labeled with bit strings of equal length in such a way that the distance between two vertices in the graph is equal to the Hamming distance between their labels. Such a labeling is called a *Hamming labeling*; it represents an isometric embedding of the partial cube into a hypercube.

**Italo Jose Dejter** is an Argentine-born American mathematician, a retired professor of mathematics and computer science and a researcher in Algebraic topology, Differential topology, Graph theory, Coding theory and Design theory. He obtained a Licentiate degree in mathematics at University of Buenos Aires in 1967, arrived at Rutgers University in 1970 by means of a Guggenheim Fellowship and obtained there a Ph.D. degree in mathematics in 1975 under the supervision of Professor Ted Petrie, with support of the National Science Foundation. He was a professor at the Federal University of Santa Catarina, Brazil, from 1977 to 1984, with grants from the National Council for Scientific and Technological Development, (CNPq).

In graph theory, the **halved cube graph** or **half cube graph** of order *n* is the graph of the demihypercube, formed by connecting pairs of vertices at distance exactly two from each other in the hypercube graph. That is, it is the half-square of the hypercube. This connectivity pattern produces two isomorphic graphs, disconnected from each other, each of which is the halved cube graph.

In the mathematical field of graph theory, a **prism graph** is a graph that has one of the prisms as its skeleton.

In graph theory, a **locally linear graph** is an undirected graph in which the neighborhood of every vertex is an induced matching. That is, for every vertex , every neighbor of should be adjacent to exactly one other neighbor of . Equivalently, every edge of such a graph belongs to a unique triangle . Locally linear graphs have also been called locally matched graphs.

- Harary, F.; Hayes, J. P.; Wu, H.-J. (1988), "A survey of the theory of hypercube graphs",
*Computers & Mathematics with Applications*,**15**(4): 277–289, doi:10.1016/0898-1221(88)90213-1, hdl: 2027.42/27522 .

This page is based on this Wikipedia article

Text is available under the CC BY-SA 4.0 license; additional terms may apply.

Images, videos and audio are available under their respective licenses.

Text is available under the CC BY-SA 4.0 license; additional terms may apply.

Images, videos and audio are available under their respective licenses.