Halved cube graph | |
Automorphisms: | , for , for , for [1] |
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 of the hypercube. This connectivity pattern produces two isomorphic graphs, disconnected from each other, each of which is the halved cube graph.
The construction of the halved cube graph can be reformulated in terms of binary numbers. 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 of the subset of binary numbers with an even number of nonzero bits (the evil numbers), and its edges connect pairs of numbers whose Hamming distance is exactly two.[2]
It is also possible to construct the halved cube graph from a lower-dimensional hypercube graph, without taking a subset of the vertices:
1 | |
2 |
Qn=
2 | |
Q | |
n-1 |
The halved cube graph
\tfrac{1}{2}Q3
\tfrac{1}{2}Q4
\tfrac{1}{2}Q5
Because it is the bipartite half of a distance-regular graph, the halved cube graph is itself distance-regular.[3] And because it contains a hypercube as a spanning subgraph, it inherits from the hypercube all monotone graph properties, such as the property of containing a Hamiltonian cycle.
As with the hypercube graphs, and their isometric (distance-preserving) subgraphs the partial cubes, a halved cube graph may be embedded isometrically into a real vector space with the Manhattan metric (L1 distance function). The same is true for the isometric subgraphs of halved cube graphs, which may be recognized in polynomial time; this forms a key subroutine for an algorithm which tests whether a given graph may be embedded isometrically into a Manhattan metric.[4]
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.[5]
The two graphs shown are symmetric Dn and Bn Petrie polygon projections (2(n - 1) and n dihedral symmetry) of the related polytope which can include overlapping edges and vertices.
n | Polytope | Graph | Vertices | Edges | ||
---|---|---|---|---|---|---|
2 | Line segment | 2 | – | |||
3 | tetrahedron | 4 | 6 | |||
4 | 16-cell | 8 | 24 | |||
5 | 5-demicube | 16 | 80 | |||
6 | 6-demicube | 32 | 240 | |||
7 | 7-demicube | 64 | 672 | |||
8 | 8-demicube | 128 | 1792 | |||
9 | 9-demicube | 256 | 4608 | |||
10 | 10-demicube | 512 | 11520 |