Halved cube graph

From Wikipedia, the free encyclopedia
Jump to: navigation, search
Halved cube graph
Demi-3-cube.svg
The halved cube graph \tfrac{1}{2}Q_3
Vertices 2n-1
Edges n(n-1)2n-3
Automorphisms n! 2n-1 , for n>4
n! 2n, for n=4
(2n-1)!, for n<4 [1]
Properties Symmetric
Distance regular
Notation \tfrac{1}{2}Q_n
Construction of two demicubes (regular tetrahedra, forming a stella octangula) from a single cube. The halved cube graph of order three is the graph of vertices and edges of a single demicube. The halved cube graph of order four includes all of the cube vertices and edges, and all of the edges of the two demicubes.

In graph theory, the halved cube graph or half cube graph of order n is the graph of the demihypercube, formed by connecting pairs of vertices at distance exactly two from each other in the hypercube graph. This connectivity pattern produces two isomorphic graphs, disconnected from each other, each of which is the halved cube graph.

Equivalent constructions[edit]

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-order hypercube graph, without taking a subset of the vertices:

\frac{1}{2}Q_n = Q_{n-1}^2

where the superscript 2 denotes the square of the hypercube graph Qn − 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 order 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[edit]

The halved cube graph \tfrac{1}{2}Q_3 of order 3 is the complete graph K4, the graph of the tetrahedron. The halved cube graph \tfrac{1}{2}Q_4 of order 4 is K2,2,2,2, the graph of the four-dimensional regular polytope, the 16-cell. The halved cube graph \tfrac{1}{2}Q_5 of order five is sometimes known as the Clebsch graph, and is the complement of the folded cube graph of order five which is more commonly called the Clebsch graph. It exists in the 5-dimensional uniform 5-polytope, the 5-demicube.

Properties[edit]

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 order 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 order three and four, four colors are needed to eliminate all symmetries.[5]

Sequence[edit]

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 Complete graph K2.svg 2
3 tetrahedron 3-demicube.svg3-demicube t0 B3.svg 4 6
4 16-cell 4-demicube t0 D4.svg4-demicube t0 B4.svg 8 24
5 5-demicube 5-demicube t0 D5.svg5-demicube t0 B5.svg 16 80
6 6-demicube 6-demicube t0 D6.svg6-demicube t0 B6.svg 32 240
7 7-demicube 7-demicube t0 D7.svg7-demicube t0 B7.svg 64 672
8 8-demicube 8-demicube t0 D8.svg8-demicube t0 B8.svg 128 1792
9 9-demicube 9-demicube t0 D9.svg9-demicube t0 B9.svg 256 4608
10 10-demicube 10-demicube.svg10-demicube graph.png 512 11520

References[edit]

  1. ^ A.E. Brouwer, A.M. Cohen, and A. Neumaier (1989), Distance Regular Graphs. Berlin, New York: Springer-Verlag, p. 265. ISBN 3-540-50619-5, ISBN 0-387-50619-5
  2. ^ Indyk, Piotr; Matoušek, Jiří (2010), "Low-distortion embeddings of finite metric spaces", in Goodman, Jacob E.; O'Rourke, Joseph, Handbook of Discrete and Computational Geometry (2nd ed.), CRC Press, p. 179, ISBN 9781420035315 .
  3. ^ Chihara, Laura; Stanton, Dennis (1986), "Association schemes and quadratic transformations for orthogonal polynomials", Graphs and Combinatorics 2 (2): 101–112, doi:10.1007/BF01788084, MR 932118 .
  4. ^ Deza, M.; Shpectorov, S. (1996), "Recognition of the l1-graphs with complexity O(nm), or football in a hypercube", European Journal of Combinatorics 17 (2-3): 279–289, doi:10.1006/eujc.1996.0024, MR 1379378 .
  5. ^ Bogstad, Bill; Cowen, Lenore J. (2004), "The distinguishing number of the hypercube", Discrete Mathematics 283 (1-3): 29–35, doi:10.1016/j.disc.2003.11.018, MR 2061481 .

External links[edit]