graph theory In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...

, the hypercube graph is the graph formed from the vertices and edges of an -dimensional

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

. For instance, the

cube graph In graph theory, the hypercube graph is the graph formed from the vertices and edges of an -dimensional hypercube. For instance, the cube graph is the graph formed by the 8 vertices and 12 edges of a three-dimensional cube. has vertices, ...

is the graph formed by the 8 vertices and 12 edges of a three-dimensional cube. has vertices, edges, and is a regular graph with edges touching each vertex. The hypercube graph may also be constructed by creating a vertex for each

subset In mathematics, set ''A'' is a subset of a set ''B'' if all elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are unequal, then ''A'' is a proper subset o ...

of an -element set, with two vertices adjacent when their subsets differ in a single element, or by creating a vertex for each -digit

binary number A binary number is a number expressed in the base-2 numeral system or binary numeral system, a method of mathematical expression which uses only two symbols: typically "0" ( zero) and "1" (one). The base-2 numeral system is a positional notati ...

, with two vertices adjacent when their binary representations differ in a single digit. It is the -fold

Cartesian product In mathematics, specifically set theory, the Cartesian product of two sets ''A'' and ''B'', denoted ''A''×''B'', is the set of all ordered pairs where ''a'' is in ''A'' and ''b'' is in ''B''. In terms of set-builder notation, that is : A\ ...

of the two-vertex

complete graph In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices ...

, and may be decomposed into two copies of 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 that is a cubic graph is the cubical graph .

Construction

The hypercube graph may be constructed from the family of subsets of a set with 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 vertices labeled with -bit

s and connecting two vertices by an edge whenever the

Hamming distance In information theory, the Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different. In other words, it measures the minimum number of ''substitutions'' required to chang ...

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 digit), and two such sets differ in a single element whenever the corresponding two binary numbers have Hamming distance one. Alternatively, may be constructed from the

disjoint union In mathematics, a disjoint union (or discriminated union) of a family of sets (A_i : i\in I) is a set A, often denoted by \bigsqcup_ A_i, with an injection of each A_i into A, such that the images of these injections form a partition of A ...

of two hypercubes , by adding an edge from each vertex in one copy of to the corresponding vertex in the other copy, as shown in the figure. The joining edges form a perfect matching. Another construction of is the

of two-vertex complete graphs . 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 consists of a single vertex, while is the

on two vertices. is a

cycle Cycle, cycles, or cyclic may refer to: Anthropology and social sciences * Cyclic history, a theory of history * Cyclical theory, a theory of American political history associated with Arthur Schlesinger, Sr. * Social cycle, various cycles in soc ...

of length . The graph is the

1-skeleton In mathematics, particularly in algebraic topology, the of a topological space presented as a simplicial complex (resp. CW complex) refers to the subspace that is the union of the simplices of (resp. cells of ) of dimensions In other word ...

of a

cube In geometry, a cube is a three-dimensional solid object bounded by six square faces, facets or sides, with three meeting at each vertex. Viewed from a corner it is a hexagon and its net is usually depicted as a cross. The cube is the on ...

and is a planar graph with eight vertices and twelve

edges Edge or EDGE may refer to: Technology Computing * Edge computing, a network load-balancing system * Edge device, an entry point to a computer network * Adobe Edge, a graphical development application * Microsoft Edge, a web browser developed by ...

. The graph is the Levi graph of the Möbius configuration. It is also the knight's graph for a toroidal

4\times 4

chessboard.

Properties

Bipartiteness

Every hypercube graph is

bipartite Bipartite may refer to: * 2 (number) * Bipartite (theology), a philosophical term describing the human duality of body and soul * Bipartite graph, in mathematics, a graph in which the vertices are partitioned into two sets and every edge has an en ...

: it can be

colored ''Colored'' (or ''coloured'') is a racial descriptor historically used in the United States during the Jim Crow Era to refer to an African American. In many places, it may be considered a slur, though it has taken on a special meaning in South ...

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 with has a Hamiltonian cycle, a cycle that visits each vertex exactly once. Additionally, a Hamiltonian path exists between two vertices and if and only if they have different colors in a -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 In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other ...

correspondence between the set of -bit cyclic Gray codes and the set of Hamiltonian cycles in the hypercube . 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. The question whether every matching extends to a Hamiltonian cycle remains an open problem.

Other properties

The hypercube graph (for ) : * is the Hasse diagram of a finite

Boolean algebra In mathematics and mathematical logic, Boolean algebra is a branch of algebra. It differs from elementary algebra in two ways. First, the values of the variables are the truth values ''true'' and ''false'', usually denoted 1 and 0, whereas ...

. * is a

median graph In graph theory, a division of mathematics, a median graph is an undirected graph in which every three vertices ''a'', ''b'', and ''c'' have a unique ''median'': a vertex ''m''(''a'',''b'',''c'') that belongs to shortest paths between each pai ...

. Every median graph is an isometric subgraph of a hypercube, and can be formed as a retraction of a hypercube. * has more than perfect matchings. (this is another consequence that follows easily from the inductive construction.) * is arc transitive and

symmetric Symmetry (from grc, συμμετρία "agreement in dimensions, due proportion, arrangement") in everyday language refers to a sense of harmonious and beautiful proportion and balance. In mathematics, "symmetry" has a more precise definit ...

. The symmetries of hypercube graphs can be represented as signed permutations. * contains all the cycles of length and is thus a bipancyclic graph. * can be drawn as a

unit distance graph In mathematics, particularly geometric graph theory, a unit distance graph is a graph formed from a collection of points in the Euclidean plane by connecting two points whenever the distance between them is exactly one. To distinguish these gr ...

in the Euclidean plane by using the construction of the hypercube graph from subsets of a set of elements, choosing a distinct unit vector for each set element, and placing the vertex corresponding to the set at the sum of the vectors in . * is a -vertex-connected graph, by Balinski's theorem * is planar (can be drawn with no crossings) if and only if . For larger values of , the hypercube has

genus Genus ( plural genera ) is a taxonomic rank used in the biological classification of living and fossil organisms as well as viruses. In the hierarchy of biological classification, genus comes above species and below family. In binomial n ...

.. * has exactly

2^\prod_^n k^

spanning tree In the mathematical field of graph theory, a spanning tree ''T'' of an undirected graph ''G'' is a subgraph that is a tree which includes all of the vertices of ''G''. In general, a graph may have several spanning trees, but a graph that is no ...

s. * has bandwidth exactly

\sum_^ \binom

. * has

achromatic number In graph theory, a complete coloring is a vertex coloring in which every pair of colors appears on ''at least'' one pair of adjacent vertices. Equivalently, a complete coloring is minimal in the sense that it cannot be transformed into a prope ...

proportional to

\sqrt

, but the constant of proportionality is not known precisely. * has as the eigenvalues of its

adjacency matrix In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph. In the special case of a finite simple ...

the numbers and as the eigenvalues of its Laplacian matrix the numbers . The th eigenvalue has multiplicity

\binom

in both cases. * has isoperimetric number . The family for all 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 In mathematics, Szymanski's conjecture, named after , states that every permutation In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a ...

concerns the suitability of a hypercube as a

network topology Network topology is the arrangement of the elements ( links, nodes, etc.) of a communication network. Network topology can be used to define or describe the arrangement of various types of telecommunication networks, including command and contr ...

for communications. It states that, no matter how one chooses a

permutation In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or p ...

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

Notes

References

* {{citation , title = A survey of the theory of hypercube graphs , authorlink1 = Frank Harary , last1 = Harary , first1 = F. , last2 = Hayes , first2 = J. P. , last3 = Wu , first3 = H.-J. , journal = Computers & Mathematics with Applications , volume = 15 , issue = 4 , pages = 277–289 , year = 1988 , doi = 10.1016/0898-1221(88)90213-1, hdl = 2027.42/27522 , hdl-access = free . Parametric families of graphs Regular graphs