Halved cube graph
In graph theory, the halved cube graph of order n is a graph 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.
The halved cube graph of order 3 is the complete graph K4, the graph of the tetrahedron. The halved cube graph of order 4 is K2,2,2,2, the graph of the four-dimensional cross polytope.
Because it is the bipartite half of a distance-regular graph, the halved cube graph is itself distance-regular.[1]
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.[2]
References
- ^ 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.