Article ID Journal Published Year Pages File Type
4653258 European Journal of Combinatorics 2016 11 Pages PDF
Abstract

Partial cubes are graphs isometrically embeddable into hypercubes. We analyze how isometric cycles in partial cubes behave and derive that every partial cube of girth more than 6 must have vertices of degree less than 3. As a direct corollary we get that every regular partial cube of girth more than 6 is an even cycle. Along the way we prove that every partial cube GG with girth more than 6 is a tree-zone graph and therefore 2n(G)−m(G)−i(G)+ce(G)=22n(G)−m(G)−i(G)+ce(G)=2 holds, where i(G)i(G) is the isometric dimension of GG and ce(G)ce(G) its convex excess.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,