Isometric embeddings of subdivided complete graphs in the hypercube

Isometric subgraphs of hypercubes are known as partial cubes. These graphs have first been investigated by Graham and Pollack [R.L Graham, H.Pollack On the addressing problem for loop switching, Bell System Technol., J. 50 (1971) 2495–2519], and Djokovic̀ [D. Djokovic̀, Distance preserving subgraphs of the hypercubes, Journal of Combinatorial Theory, Ser B41 (1973), 263–267]. Several papers followed with various characterizations of partial cubes. In this paper, we prove that a subdivision of a complete graph of order n(n⩾4), is a partial cube if and only if this one is isomorphic to S(Kn), or there exist n−1 non-subdivided edges of Kn adjacent to a common vertex in the subdivision and the other edges of Kn are subdivided an odd number of times.