Classification of vertex-transitive cubic partial cubes

2015/09/15 by Marc, Tilen · 1 citation
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.1509.04565

Abstract

Partial cubes are graphs isometrically embeddable into hypercubes. In this paper it is proved that every cubic, vertex-transitive partial cube is isomorphic to one of the following graphs: K₂ \square C_2n, for some n≥ 2, 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.~from 2004 on cubic mirror graphs, it includes all cubic, distance-regular partial cubes (Weichsel, 1992), and presents a contribution to the classification of all cubic partial cubes.

Cited by

• Cubic vertex-transitive graphs of girth seven

Related

• Partial cubes: structures, characterizations, and constructions
• Two-dimensional partial cubes
• Hypercellular graphs: partial cubes without Q₃^- as partial cube minor
• Cubic vertex-transitive graphs on up to 1280 vertices
• Partial cubes with pre-hull number at most 1