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 halved cube graph or half cube graph of dimension is the

graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discre ...

of the

demihypercube In geometry, demihypercubes (also called ''n-demicubes'', ''n-hemicubes'', and ''half measure polytopes'') are a class of ''n''-polytopes constructed from alternation of an ''n''-hypercube, labeled as ''hγn'' for being ''half'' of the hype ...

, formed by connecting pairs of vertices at

distance Distance is a numerical or occasionally qualitative measurement of how far apart objects or points are. In physics or everyday usage, distance may refer to a physical length or an estimation based on other criteria (e.g. "two counties over"). ...

exactly two from each other in the

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

. That is, it is the

half-square In graph theory, the bipartite half or half-square of a bipartite graph is a graph whose vertex set is one of the two sides of the bipartition (without loss of generality, ) and in which there is an edge for each pair of vertices in that ar ...

of the hypercube. This connectivity pattern produces two isomorphic graphs, disconnected from each other, each of which is the halved cube graph.

Equivalent constructions

The construction of the halved cube graph can be reformulated in terms of

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. The vertices of a hypercube may be labeled by binary numbers in such a way that two vertices are adjacent exactly when they differ in a single bit. The demicube may be constructed from the hypercube as the

convex hull In geometry, the convex hull or convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space ...

of the subset of binary numbers with an even number of nonzero bits (the

evil number In number theory, an evil number is a non-negative integer that has an even Hamming weight, number of 1s in its Binary number, binary expansion. These numbers give the positions of the zero values in the Thue–Morse sequence, and for this reason ...

s), and its edges connect pairs of numbers whose

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

is exactly two. It is also possible to construct the halved cube graph from a lower-dimensional hypercube graph, without taking a subset of the vertices: :

\fracQ_n = Q_^2

where the superscript 2 denotes the

square In Euclidean geometry, a square is a regular quadrilateral, which means that it has four equal sides and four equal angles (90-degree angles, π/2 radian angles, or right angles). It can also be defined as a rectangle with two equal-length adj ...

of the hypercube graph ''Q''_{''n'' − 1}, the graph formed by connecting pairs of vertices whose distance is at most two in the original graph. For instance, the halved cube graph of dimension four may be formed from an ordinary three-dimensional cube by keeping the cube edges and adding edges connecting pairs of vertices that are on opposite corners of the same square face.

Examples

The halved cube graph

\tfracQ_3

of dimension 3 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 ...

''K''₄, the graph of the

tetrahedron In geometry, a tetrahedron (plural: tetrahedra or tetrahedrons), also known as a triangular pyramid, is a polyhedron composed of four triangular faces, six straight edges, and four vertex corners. The tetrahedron is the simplest of all the o ...

. The halved cube graph

\tfracQ_4

of dimension 4 is ''K''_2,2,2,2, the graph of the four-dimensional regular polytope, the

16-cell In geometry, the 16-cell is the regular convex 4-polytope (four-dimensional analogue of a Platonic solid) with Schläfli symbol . It is one of the six regular convex 4-polytopes first described by the Swiss mathematician Ludwig Schläfli in the mi ...

. The halved cube graph

\tfracQ_5

of dimension five is sometimes known as the

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 graph is the dimension-5 halved cube graph; it wa ...

, and is the complement of the

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

of dimension five, which is the one more commonly called the Clebsch graph. It exists in the 5-dimensional

uniform 5-polytope In geometry, a uniform 5-polytope is a five-dimensional uniform polytope. By definition, a uniform 5-polytope is vertex-transitive and constructed from uniform 4-polytope Facet (geometry), facets. The complete set of convex uniform 5-polytopes ...

, the

5-demicube In five-dimensional geometry, a demipenteract or 5-demicube is a semiregular 5-polytope, constructed from a ''5-hypercube'' (penteract) with alternated vertices removed. It was discovered by Thorold Gosset. Since it was the only semiregular 5- ...

Properties

Because it is the

bipartite half In graph theory, the bipartite half or half-square of a bipartite graph is a graph whose vertex set is one of the two sides of the bipartition (without loss of generality, ) and in which there is an edge for each pair of vertices in that are ...

of a

distance-regular graph In the mathematical field of graph theory, a distance-regular graph is a regular graph such that for any two vertices and , the number of vertices at distance from and at distance from depends only upon , , and the distance between and . ...

, the halved cube graph is itself distance-regular. And because it contains a hypercube as a

spanning subgraph This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges. Symbols A B ...

, it inherits from the hypercube all monotone graph properties, such as the property of containing 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 ...

. As with the hypercube graphs, and their isometric (distance-preserving) subgraphs the

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

s, a halved cube graph may be embedded isometrically into a

real vector space Real may refer to: Currencies * Brazilian real (R$) * Central American Republic real * Mexican real * Portuguese real * Spanish real * Spanish colonial real Music Albums * ''Real'' (L'Arc-en-Ciel album) (2000) * ''Real'' (Bright album) (2010) ...

with the

Manhattan metric A taxicab geometry or a Manhattan geometry is a geometry whose usual distance function or metric of Euclidean geometry is replaced by a new metric in which the distance between two points is the sum of the absolute differences of their Cartesian co ...

(''L''₁ distance function). The same is true for the isometric subgraphs of halved cube graphs, which may be recognized in

polynomial time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...

; this forms a key subroutine for an algorithm which tests whether a given graph may be embedded isometrically into a Manhattan metric. For every halved cube graph of dimension five or more, it is possible to (improperly) color the vertices with two colors, in such a way that the resulting colored graph has no nontrivial symmetries. For the graphs of dimension three and four, four colors are needed to eliminate all symmetries..

Sequence

The two graphs shown are symmetric ''D''_''n'' and ''B''_''n''

Petrie polygon In geometry, a Petrie polygon for a regular polytope of dimensions is a skew polygon in which every consecutive sides (but no ) belongs to one of the facets. The Petrie polygon of a regular polygon is the regular polygon itself; that of a reg ...

projections (2(''n'' − 1) and ''n''

dihedral symmetry In mathematics, a dihedral group is the group of symmetries of a regular polygon, which includes rotations and reflections. Dihedral groups are among the simplest examples of finite groups, and they play an important role in group theory, ge ...

) of the related polytope which can include overlapping edges and vertices.

References

External links

*{{mathworld, id=HalvedCubeGraph, title=Halved Cube Graph Parametric families of graphs Regular graphs