Classification of Vertex‐Transitive Cubic Partial Cubes
Tilen Marc · Journal of Graph Theory · 2017
Abstract Partial cubes are graphs isometrically embeddable into hypercubes. In this article, it is proved that every cubic, vertex‐transitive partial cube is isomorphic to one of the following graphs: , for , the generalized Petersen graph G(10, 3), the cubic permutahedron, the truncated cuboctahedron, or the truncated icosidodecahedron. This classification is a generalization of results of Brešar et al. (Eur J Combin 25 (2004), 55–64) on cubic mirror graphs; it includes all cubic, distance‐regular partial cubes (P. M. Weichsel, Discrete Math 109 (1992), 297–306), and presents a contribution to the classification of all cubic partial cubes.