pith. sign in

arxiv: 1503.04706 · v2 · pith:VGOARD7Vnew · submitted 2015-03-16 · 💻 cs.DM · math.CO

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

classification 💻 cs.DM math.CO
keywords partialgirthcubecubeseverydegreeisometricalong
0
0 comments X
read the original 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 $G$ with girth more than 6 is a tree-zone graph and therefore $2n(G)-m(G)-i(G)+ce(G)=2$ holds, where $i(G)$ is the isometric dimension of $G$ and $ce(G)$ its convex excess.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.