Isometric embedding of subdivided Connected graphs in the hypercube

Isometric subgraphs of hypercubes are known as partial cubes. These graphs have first been investigated by Graham and Pollak [R.L Graham, H.Pollak 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, J. Combin. Theory, Ser B41 (1973), 263–267]. Several papers followed with various characterizations of partial cubes. In this paper, we determine all subdivisions of a given configuration which can be embedded isometrically in the hypercube. More specially, we deal with the case where this configuration is a connected graph of order 4 on one hand and the case where the configuration is a fan F k ( k ⩾ 3 ) on the other hand. Finally, we conjecture that a subdivision of a complete graph of order n ( n ⩾ 5 ) is a partial cube if and only if this one is isomorphic to S ( K n ) or there exists n − 1 edges of K n adjacent to a common vertex in the subdivision and the other edges of K n contain odd added vertices. This proposition is true when the order n ∈ { 4 , 5 , 6 } .