This evening I'm reading “Isometric Embeddings of Subdivided Complete Graphs in the Hypercube,” by Beaudou, Gravier, and Meslem [SIAM J. Discrete Math. 22(3): 1226–1238, 2008; there's also an earlier version online from Eurocomb 2007].

Another way of describing an isometric embedding into a hypercube is that it's a way of labeling vertices of a graph by sets, in such a way that the Hamming distance of the set labels is the same as the graph distance. For a clique in which every edge has been subdivided by a single vertex (such as the subdivision of \(K_8\) below), such a labeling is easy to find: simply use a singleton set for each of the original clique vertices, and a doubleton for the subdivision vertices.

Subdivision of K_8

In the other class of subdivided cliques that have an isometric hypercube embedding, there is one central clique vertex (shown red in the subdivided \(K_6\) below) such that all incident clique edges are unsubdivided, and every other clique edge has been subdivided by adding an odd number of vertices along it (the small white vertices in the figure). For these graphs, a labeling can be found by using the empty set for the central vertex, and singleton sets for the other original clique vertices (green in the figure). A subdivision vertex on an edge that has been subdivided only once can be represented by a doubleton, but we need to do something a little more complicated involving the introduction of additional set elements for the clique edges with larger numbers of subdivision vertices. Perhaps it's worth pointing out that some of the edges could also be deleted instead of subdivided and the result would still be a partial cube.

Subdivision of K_6

The hard part of the paper (and the part that, to be frank, I didn't find very enlightening) is the proof that these are the only possibilities: any other subdivided clique is not a partial cube. The authors claim in the abstract that this result shows that any graph is a minor of a partial cube, but I think we knew that already (it follows merely from the fact that hypercubes have nonlinear numbers of edges) and it's not mentioned in the text of the paper. But I think this result is interesting in that it finds a broad class of sparse graphs that are examples of partial cubes.