Cubic graphs with large circumference deficit

DOI10.1002/JGT.21911MaRDI QIDQ3188672zbMATH OpenOpenAlexFDO

Authors E. Máčajová, J. Mazák

Publication date 12 August 2016

Published in Journal of Graph Theory (Search for Journal in Brave)

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

zbMATH Keywords

circumferencecubic graphgirthsnark

Mathematics Subject Classification ID

Distance in graphs (05C12) Paths and cycles (05C38) Connectivity (05C40)

Abstract: The circumference $c(G)$ of a graph $G$ is the length of a longest cycle. By exploiting our recent results on resistance of snarks, we construct infinite classes of cyclically $4$-, $5$- and $6$-edge-connected cubic graphs with circumference ratio $c(G)/|V(G)|$ bounded from above by $0.876$, $0.960$ and $0.990$, respectively. In contrast, the dominating cycle conjecture implies that the circumference ratio of a cyclically $4$-edge-connected cubic graph is at least $0.75$. In addition, we construct snarks with large girth and large circumference deficit, solving Problem 1 proposed in [J. H"agglund and K. Markstr"om, On stable cycles and cycle double covers of graphs with large circumference, Disc. Math. 312 (2012), 2540--2544].

Recommendations

• Circumference of 3-connected cubic graphs
• On the circumference of 3-connected cubic triangle-free plane graphs
• Cubic graphs with no short cycle covers
• Some results and problems about circumferences of graphs
• A note on 3-connected cubic planar graphs

Cites work

• Circumference of 3-connected claw-free graphs and large Eulerian subgraphs of 3-edge-connected graphs
• Circumference of Graphs with Bounded Degree
• Classification and characterizations of snarks
• Generation and properties of snarks
• scientific article; zbMATH DE number 4106897 (Why is no real title available?)
• scientific article; zbMATH DE number 874369 (Why is no real title available?)
• Longest Cycles in 2-Connected Graphs with Prescribed Maximum Degree
• Longest Cycles in 3-Connected 3-Regular Graphs
• Longest cycles in 3-connected cubic graphs
• Measurements of edge-uncolorability
• On stable cycles and cycle double covers of graphs with large circumference
• Reducible configurations for the cycle double cover conjecture
• Snarks without small cycles

Cited in

(6)

• Cuts in matchings of 3-connected cubic graphs
• Circumference of 3-connected cubic graphs
• Shortness coefficient of cyclically 4-edge-connected cubic graphs
• The smallest nontrivial snarks of oddness 4
• scientific article; zbMATH DE number 426156 (Why is no real title available?)
• Circumference of essentially 4-connected planar triangulations

This page was built for publication: Cubic graphs with large circumference deficit

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