Hypercube graph

From Wikipedia, the free encyclopedia

In the mathematical field of graph theory, the hypercube graph Q_n is a special regular graph with 2ⁿ 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 Q_n is incident to exactly n edges (that is, Q_n is n-regular), so the total number of edges is 2ⁿ⁻¹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. 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.

Hypercube graphs are arc transitive (symmetric). The symmetries of hypercube graphs can be represented as signed permutations.

The name comes from the fact that the hypercube graph is the one-dimensional skeleton of the geometric hypercube. The graph is also the Hasse diagram of a finite Boolean algebra. It is the Cartesian product of two-vertex complete graphs K₂. An important presentation of the hypercube graph arises from the fact that the vertices 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).

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 Q₃.

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 Q₀ consists of a single vertex, while Q₁ is the complete graph on two vertices and Q₂ is a cycle of length 4.

The graph Q₃ is the skeleton of a cube, a planar graph with eight vertices and twelve edges. Q_n is planar if and only if n ≤ 3.

[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.

• Mills, W. H. (1963). "Some complete cycles on the n-cube". Proceedings of the American Mathematical Society: 640–643.