Cycle lengths modulo k in large 3-connected cubic graphs

DOI10.19086/AIC.18971MaRDI QIDQ5162867zbMATH OpenOpenAlexFDO

Authors Kasper Szabo Lyngsie, Martin Merker

Publication date 5 November 2021

Published in Advances in Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

cubic graphs

Mathematics Subject Classification ID

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

Abstract: We prove that for all natural numbers $m$ and $k$ where $k$ is odd, there exists a natural number $N(k)$ such that any 3-connected cubic graph with at least $N(k)$ vertices contains a cycle of length $m$ modulo $k$. We also construct a family of graphs showing that this is not true for 2-connected cubic graphs if $m$ and $k$ are divisible by 3 and $kgeq12$.

Recommendations

• Gaps in the cycle spectrum of 3-connected cubic planar graphs
• scientific article; zbMATH DE number 867680
• Graphs with a cycle of length divisible by three
• scientific article; zbMATH DE number 3906529
• scientific article; zbMATH DE number 617590

Cites work

• Cycle lengths and minimum degree of graphs
• Cycle lengths in sparse graphs
• Cycles Modulo k
• Cycles of even lengths modulo k
• Cycles of length 0 modulo 4 in graphs
• Cycles of length 1 modulo 3 in graph
• Cycles of length 2 modulo 3 in graphs
• Cycles with consecutive odd lengths
• Distribution of cycle lengths in graphs
• Girth in graphs
• Graph decomposition with applications to subdivisions and path systems modulo k
• Graphs with a cycle of length divisible by three
• scientific article; zbMATH DE number 3547317 (Why is no real title available?)
• scientific article; zbMATH DE number 1117463 (Why is no real title available?)
• scientific article; zbMATH DE number 3279777 (Why is no real title available?)
• scientific article; zbMATH DE number 3019031 (Why is no real title available?)
• On arithmetic progressions of cycle lengths in graphs
• Open problems of Paul Erd�s in graph theory
• Pancyclicity mod \(k\) of claw-free graphs and \(K_{1,4}\)-free graphs
• The extremal function for cycles of length \(\ell\) mod \(k\)
• Unavoidable cycle lengths in graphs

Cited in

(15)

• Cycles of length 2 modulo 3 in graphs
• Tight cycle spectrum gaps of cubic 3-connected toroidal graphs
• Cycle lengths modulo k in expanders
• Counterexamples to a conjecture of Merker on 3-connected cubic planar graphs with a large cycle spectrum gap
• Modification of CZ₃-free condition to have a cycle containing specified vertices
• scientific article; zbMATH DE number 3906529 (Why is no real title available?)
• On path lengths modulo three
• Modularity of cycles and paths in graphs
• scientific article; zbMATH DE number 867680 (Why is no real title available?)
• scientific article; zbMATH DE number 867697 (Why is no real title available?)
• Complete minors in cubic graphs with few short cycles and random cubic graphs.
• The \(3x+1\) problem: New lower bounds on nontrivial cycle lengths
• On the divisibility of the cycle number by 7
• A strengthening on consecutive odd cycles in graphs of given minimum degree
• Linked graphs with restricted lengths

This page was built for publication: Cycle lengths modulo \(k\) in large 3-connected cubic graphs

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