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

DOI10.1016/J.EJC.2016.01.005MaRDI QIDQ268262zbMATH OpenOpenAlexFDO

Authors Tilen Marc

Publication date 14 April 2016

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1503.04706

zbMATH Keywords

isometrically embeddable graphs

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

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.

Recommendations

• Partial cubes: Structures, characterizations, and constructions
• Hunting for cubic partial cubes
• scientific article; zbMATH DE number 1998298
• Convex excess in partial cubes
• Partial cubes as subdivision graphs and as generalized Petersen graphs

Cites work

• scientific article; zbMATH DE number 1339499 (Why is no real title available?)
• scientific article; zbMATH DE number 1998298 (Why is no real title available?)
• scientific article; zbMATH DE number 6475965 (Why is no real title available?)
• n‐cubes and median graphs
• A poset-based approach to embedding median graphs in hypercubes and lattices
• Antipodal graphs and oriented matroids
• Convex excess in partial cubes
• Convexity in partial cubes: the hull number
• Cubic inflation, mirror graphs, regular maps, and partial cubes
• Cubic partial cubes from simplicial arrangements
• Distance regular subgraphs of a cube
• Geometry of cuts and metrics
• Handbook of product graphs
• Infinite median graphs, (0, 2)-graphs, and hypercubes
• Isometric embedding in products of complete graphs
• Media theory. Interdisciplinary applied mathematics.
• Netlike partial cubes. I. General properties
• On the Addressing Problem for Loop Switching
• Oriented Matroids
• Partial cubes: Structures, characterizations, and constructions
• Regular median graphs of linear growth
• Retracts of hypercubes
• The hypergraph of \(\Theta \)-classes and \(\Theta \)-graphs of partial cubes.
• Transitive, locally finite median graphs with finite blocks
• Tree-like partial Hamming graphs
• Tribes of cubic partial cubes
• Vertex-transitive median graphs of non-exponential growth

Cited in

(9)

• Daisy cubes and distance cube polynomial
• On antipodal and diametrical partial cubes
• COMs: complexes of oriented matroids
• Mirror graphs: graph theoretical characterization of reflection arrangements and finite Coxeter groups
• Characterization of 2-arc-transitive partial cubes
• A characterization of regular partial cubes whose all convex cycles have the same lengths
• On some characterizations of antipodal partial cubes
• On some properties of antipodal partial cubes
• On tope graphs of complexes of oriented matroids

This page was built for publication: There are no finite partial cubes of girth more than 6 and minimum degree at least 3

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q268262)