In
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
![Hypercubeconstruction](https://upload.wikimedia.org/wikipedia/commons/a/aa/Hypercubeconstruction.png)
The hypercube graph may be constructed from the family of
subsets
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 of ...
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
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 ...
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
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 ...
.
Another construction of is the
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 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
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 ...
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 form ...
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 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
![Gray_code_tesseract](https://upload.wikimedia.org/wikipedia/commons/c/c2/Gray_code_tesseract.svg)
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 s ...
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 graph ...
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 g ...
* 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
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
.
* 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
, 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
in both cases.
* has
isoperimetric number
In mathematics, the Cheeger constant (also Cheeger number or isoperimetric number) of a graph is a numerical measure of whether or not a graph has a "bottleneck". The Cheeger constant as a measure of "bottleneckedness" is of great interest in man ...
.
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 may ...
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 ge ...
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.
[.]
See also
*
de Bruijn graph
In graph theory, an -dimensional De Bruijn graph of symbols is a directed graph representing overlaps between sequences of symbols. It has vertices, consisting of all possible sequences of the given symbols; the same symbol may appear multiple ...
*
Cube-connected cycles
In graph theory, the cube-connected cycles is an undirected cubic graph, formed by replacing each vertex of a hypercube graph by a cycle. It was introduced by for use as a network topology in parallel computing.
Definition
The cube-connected c ...
*
Fibonacci cube
In the mathematical field of graph theory, the Fibonacci cubes or Fibonacci networks are a family of undirected graphs with rich recursive properties derived from its origin in number theory. Mathematically they are similar to the hypercube graphs ...
*
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.
Construction
The folded cube graph of dimension ''k'' (containin ...
*
Frankl–Rödl graph
In graph theory and computational complexity theory, a Frankl–Rödl graph is a graph defined by connecting pairs of vertices of a hypercube that are at a specified even distance from each other. The graphs of this type are parameterized by the d ...
*
Halved cube graph
In graph theory, the halved cube graph or half cube graph of dimension 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 o ...
*
Hypercube internetwork topology In computer networking, hypercube networks are a type of network topology used to connect multiple processors with memory modules and accurately route data. Hypercube networks consist of nodes, which form the vertices of squares to create an inte ...
*
Partial cube
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 cu ...
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