Isometric Embeddings of Subdivided Complete Graphs in the Hypercube
Laurent Beaudou, Sylvain Gravier, Kahina Meslem · SIAM Journal on Discrete Mathematics · 2008
Isometric subgraphs of hypercubes are known as partial cubes. These graphs have first been investigated by Graham and Pollak [Bell System Tech. J., 50 (1971), pp. 2495–2519] and Djoković [J. Combinatorial Theory Ser. B, 14 (1973), pp. 263–267]. Several papers followed with various characterizations of partial cubes. In this paper, it is proven that a subdivision of a complete graph of order n ($n \geq 4$) is a partial cube if and only if it is isomorphic to $S(K_n)$ or there exist $n-1$ nonsubdivided edges of $K_n$ adjacent to a common vertex in the subdivision and the other edges of $K_n$ are subdivided an odd number of times. As a corollary, we build partial cubes with arbitrary graph as a minor.