Hypercube graph
From Wikipedia, the free encyclopedia
| Hypercube graph | |
 The hypercube graph Q4 |
|
| Vertices | 2n |
|---|---|
| Edges | 2n−1n |
| Properties | Arc-transitive Unit distance |
In the mathematical field of graph theory, the hypercube graph Qn is a special regular graph with 2n vertices, which correspond to the subsets of a set with n elements. Two vertices labelled by subsets S and T are joined by an edge if and only if S can be obtained from T by adding or removing a single element. Each vertex of Qn is incident to exactly n edges (that is, Qn is n-regular), so the total number of edges is 2n−1n.
The name comes from the fact that the hypercube graph is the one-dimensional skeleton of the geometric hypercube.
Hypercube graphs should not be confused with cubic graphs, which are graphs that are 3-regular. The only hypercube that is a cubic graph is Q3.
Contents |
[edit] Properties
The hypercube graph Qn is the Hasse diagram of a finite Boolean algebra. It is the Cartesian product of n two-vertex complete graphs K2. Its distance is the same as the Hamming distance on the set of binary strigs of length n.
Every hypercube is a bipartite graph, because two subsets S and T can represent adjacent vertices only if S has odd cardinality and T has even cardinality, or vice versa.
Every hypercube is a median graph. Every median graph is an isometric subgraph of a hypercube, and can be formed as a retraction of a hypercube.
Hypercube graphs are arc transitive (symmetric). The symmetries of hypercube graphs can be represented as signed permutations.
Any hypercube graph can be drawn as a unit distance graph in the Euclidean plane by choosing a unit vector for each set element and placing each vertex corresponding to a set S at the sum of the vectors in S.
An important presentation of the hypercube graph arises from the fact that the vertices can be labeled by strings of n bits so that two bit strings represent adjacent vertices if and only if they agree in exactly n−1 positions. The distance between vertices in the graph is then equal to the Hamming distance of the vertices' labels. Via this labeling, a Gray code can be viewed as a Hamiltonian cycle of a hypercube (Mills 1963). The Hamming distance represents the minimum distance a message must travel in a hypercube computer architecture, a form of Wormhole routing.
[edit] Problems
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.
[edit] Examples
The graph Q0 consists of a single vertex, while Q1 is the complete graph on two vertices and Q2 is a cycle of length 4.
The graph Q3 is the skeleton of a cube, a planar graph with eight vertices and twelve edges. Qn is planar if and only if n ≤ 3.
[edit] See also
[edit] References
- 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.
- Mills, W. H. (1963), “Some complete cycles on the n-cube”, Proceedings of the American Mathematical Society 14: 640–643, DOI 10.2307/2034292.
