Halved cube graph
| Halved cube graph | |
|---|---|
 The halved cube graph ½Q4 | |
| Vertices | 2n-1 |
| Edges | n(n-1)2n-3 |
| Automorphisms | n! 2n-1 |
| Properties | Symmetric Distance regular Unit distance |
| Notation | ½Qn |
| Table of graphs and parameters | |
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. Alternatively and equivalently, the halved cube graph may be constructed by choosing a vertex for each bitstring of length n with even Hamming weight, and by connecting pairs of vertices by an edge when their Hamming distance is exactly two.[1]
The halved cube graph of order 3, ½Q3 is the complete graph K4, the graph of the tetrahedron. The halved cube graph of order 4, ½Q4 is K2,2,2,2, the graph of the four-dimensional regular polytope, the 16-cell. The halved cube graph of order five, ½Q5 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.
Because it is the bipartite half of a distance-regular graph, the halved cube graph is itself distance-regular.[2]
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.[3]
References
- ^ Indyk, Piotr; Matoušek, Jiří (2010), "Low-distortion embeddings of finite metric spaces", in Goodman, Jacob E.; O'Rourke, Joseph (eds.), Handbook of Discrete and Computational Geometry (2nd ed.), CRC Press, p. 179, ISBN 9781420035315.
- ^ 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 0932118.
- ^ 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.