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

DOI10.1016/J.EJC.2016.01.005zbMATH Open1333.05205arXiv1503.04706OpenAlexW2276257166MaRDI QIDQ268262FDOQ268262

Authors: Tilen Marc 

Publication date: 14 April 2016

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

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.

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

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

zbMATH Keywords

isometrically embeddable graphs

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (9)

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

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)