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

, 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 is the graph formed by the 8 vertices and 12 edges of a three-dimensional cube. has vertices, edges, and is a

regular graph In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegree o ...

with edges touching each vertex. The hypercube graph may also be constructed by creating a vertex for each

subset In mathematics, Set (mathematics), set ''A'' is a subset of a set ''B'' if all Element (mathematics), 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 ...

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

, 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\ti ...

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

, and may be decomposed into two copies of connected to each other by a

perfect matching In graph theory, a perfect matching in a graph is a matching that covers every vertex of the graph. More formally, given a graph , a perfect matching in is a subset of edge set , such that every vertex in the vertex set is adjacent to exactly ...

. Hypercube graphs should not be confused with

cubic graph In the mathematical field of graph theory, a cubic graph is a graph in which all vertices have degree three. In other words, a cubic graph is a 3-regular graph. Cubic graphs are also called trivalent graphs. A bicubic graph is a cubic bipa ...

s, 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 Set, The Set, SET or SETS may refer to: Science, technology, and mathematics Mathematics *Set (mathematics), a collection of elements *Category of sets, the category whose objects and morphisms are sets and total functions, respectively Electro ...

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

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

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

. 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 Hamming graphs are a special class of graphs named after Richard Hamming and used in several branches of mathematics (graph theory) and computer science. Let be a set of elements and a positive integer. The Hamming graph has vertex set , ...

; 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 of length . The graph is the 1-skeleton 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 only r ...

and is a planar graph with eight vertices and twelve edges. The graph is the

Levi graph In combinatorial mathematics, a Levi graph or incidence graph is a bipartite graph associated with an incidence structure.. See in particulap. 181 From a collection of points and lines in an incidence geometry or a projective configuration, we fo ...

of the

Möbius configuration In geometry, the Möbius configuration or Möbius tetrads is a certain configuration in Euclidean space or projective space, consisting of two mutually inscribed tetrahedra: each vertex of one tetrahedron lies on a face plane of the other tetrahed ...

. It is also the knight's graph for a toroidal

4\times 4

chessboard A chessboard is a used to play chess. It consists of 64 squares, 8 rows by 8 columns, on which the chess pieces are placed. It is square in shape and uses two colours of squares, one light and one dark, in a chequered pattern. During play, the bo ...

Properties

Bipartiteness

Every hypercube graph is bipartite: it can be

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

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 In the mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a cycle that visits each vertex ...

, a cycle that visits each vertex exactly once. Additionally, a

Hamiltonian path In the mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a cycle that visits each vertex ...

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 Induction, Inducible or Inductive may refer to: Biology and medicine * Labor induction (birth/pregnancy) * Induction chemotherapy, in medicine * Induced stem cells, stem cells derived from somatic, reproductive, pluripotent or other cell t ...

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 The reflected binary code (RBC), also known as reflected binary (RB) or Gray code after Frank Gray, is an ordering of the binary numeral system such that two successive values differ in only one bit (binary digit). For example, the representat ...

. 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 In order theory, a Hasse diagram (; ) is a type of mathematical diagram used to represent a finite partially ordered set, in the form of a drawing of its transitive reduction. Concretely, for a partially ordered set ''(S, ≤)'' one represents ea ...

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

. * 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 pair o ...

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

. The symmetries of hypercube graphs can be represented as

signed permutations In mathematics, a generalized permutation matrix (or monomial matrix) is a matrix with the same nonzero pattern as a permutation matrix, i.e. there is exactly one nonzero entry in each row and each column. Unlike a permutation matrix, where the non ...

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

in the Euclidean plane by using the construction of the hypercube graph from subsets of a set of elements, choosing a distinct

unit vector In mathematics, a unit vector in a normed vector space is a vector (often a spatial vector) of length 1. A unit vector is often denoted by a lowercase letter with a circumflex, or "hat", as in \hat (pronounced "v-hat"). The term ''direction vecto ...

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 In polyhedral combinatorics, a branch of mathematics, Balinski's theorem is a statement about the graph-theoretic structure of three-dimensional convex polyhedra and higher-dimensional convex polytopes. It states that, if one forms an undirected ...

* is

planar Planar is an adjective meaning "relating to a plane (geometry)". Planar may also refer to: Science and technology * Planar (computer graphics), computer graphics pixel information from several bitplanes * Planar (transmission line technologies), ...

(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 extant taxon, living and fossil organisms as well as Virus classification#ICTV classification, viruses. In the hierarchy of biological classification, genus com ...

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

s. * has

bandwidth Bandwidth commonly refers to: * Bandwidth (signal processing) or ''analog bandwidth'', ''frequency bandwidth'', or ''radio bandwidth'', a measure of the width of a frequency range * Bandwidth (computing), the rate of data transfer, bit rate or thr ...

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

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

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 In graph theory and theoretical computer science, the longest path problem is the problem of finding a simple path of maximum length in a given graph. A path is called ''simple'' if it does not have any repeated vertices; the length of a path ma ...

or cycle that is an

induced subgraph In the mathematical field of graph theory, an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and ''all'' of the edges (from the original graph) connecting pairs of vertices in that subset. Defini ...

of a given hypercube graph is known as the

snake-in-the-box The snake-in-the-box problem in graph theory and computer science deals with finding a certain kind of path along the edges of a hypercube. This path starts at one corner and travels along the edges to as many corners as it can reach. After it g ...

problem. Szymanski's conjecture 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 contro ...

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

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