There are no finite partial cubes of girth more than 6 and minimum degree at least 3

preprint2016arXivOpen access

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.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.