Hypercube graph

Last updated
Hypercube graph
Hypercubestar.svg
The hypercube graph Q4
Vertices 2n
Edges 2n1n
Diameter n
Girth 4 if n ≥ 2
Automorphisms n! 2n
Chromatic number 2
Spectrum
Properties Symmetric
Distance regular
Unit distance
Hamiltonian
Bipartite
NotationQn
Table of graphs and parameters

In graph theory, the hypercube graphQn is the graph formed from the vertices and edges of an n-dimensional hypercube. For instance, the cubical graph Q3 is the graph formed by the 8 vertices and 12 edges of a three-dimensional cube. Qn has 2n vertices, 2n1n edges, and is a regular graph with n edges touching each vertex.

Contents

The hypercube graph Qn 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 Qn 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 Qn that is a cubic graph is the cubical graph Q3.

Construction

Construction of Q3 by connecting pairs of corresponding vertices in two copies of Q2 Hypercubeconstruction.png
Construction of Q3 by connecting pairs of corresponding vertices in two copies of Q2

The hypercube graph Qn 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 2n 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, Qn may be constructed from the disjoint union of two hypercubes Qn 1, by adding an edge from each vertex in one copy of Qn 1 to the corresponding vertex in the other copy, as shown in the figure. The joining edges form a perfect matching.

Another construction of Qn is the Cartesian product of n two-vertex complete graphs K2. More generally the Cartesian product of copies of a complete graph is called a Hamming graph; the hypercube graphs are examples of Hamming graphs.

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 1-skeleton of a cube, a cubical graph, a planar graph with eight vertices and twelve edges.

The graph Q4 is the Levi graph of the Möbius configuration. It is also the knight's graph for a toroidal chessboard. [1]

Properties

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.

Hamiltonicity

Every hypercube Qn 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 Qn. [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]

Other properties

The hypercube graph Qn (for n > 1) :

The family Qn for all n > 1 is a Lévy family of graphs

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.

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]

See also

Notes

  1. Watkins, John J. (2004), Across the Board: The Mathematics of Chessboard Problems, Princeton University Press, p. 68, ISBN   978-0-691-15498-5 .
  2. 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 .
  3. 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 .
  4. Ruskey, F. and Savage, C. Matchings extend to Hamiltonian cycles in hypercubes on Open Problem Garden. 2007.
  5. Ringel, G. (1955), "Über drei kombinatorische Probleme am n-dimensionalen Wiirfel und Wiirfelgitter", Abh. Math. Sem. Univ. Hamburg, 20: 10–19, MR   0949280
  6. 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 .
  7. Optimal Numberings and Isoperimetric Problems on Graphs, L.H. Harper, Journal of Combinatorial Theory, 1, 385393, doi : 10.1016/S0021-9800(66)80059-5
  8. 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 .
  9. 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.

Related Research Articles

Cube A geometric shape with 6 square faces

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.

Hypercube Convex polytope, the n-dimensional analogue of a square and a cube

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 .

Petersen graph

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.

Bipartite graph

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.

Desargues graph

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.

Kneser graph

In graph theory, the Kneser graphK(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.

Möbius–Kantor graph

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 complex

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 2n vertices is an undirected graph with two sets of vertices {u1, u2, ..., un} and {v1, v2, ..., vn} and with an edge from ui to vj whenever i ≠ j.

Odd graph

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

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

Hamiltonian decomposition

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.

Folded cube graph

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

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

Halved cube graph

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.

Locally linear graph

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.

References