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.

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

Contents 1 Properties 2 Problems 3 Examples 4 References

[edit] Properties

A hypercube graph is the Hasse diagram of a finite Boolean algebra. It is the Cartesian product of two-vertex complete graphs K₂.

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.

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