Partial cubes as subdivision graphs and as generalized Petersen graphs

摘要

Isometric subgraphs of hypercubes are known as partial cubes. The subdivision graph of a graph G is obtained from G by subdividing every edge of G. It is proved that for a connected graph G its subdivision graph is a partial cube if and only if every block of G is either a cycle or a complete graph. Regular partial cubes are also considered. In particular, it is shown that among the generalized Petersen graphs P(10,3) and P(2n,1), n ≥ 2, are the only (regular) partial cubes.