Compatible cycles in cubic graphs of small order

Salehi Nowbandegani, Esfandiari, Shirdareh Haghighi and Bibak conjectured that every cubic graph contains a cycle of some length ℓ for which the interval [2ℓ, 3ℓ] contains a power of two; by contracting triangles, this would imply the Erdős–Gyárfás conjecture for claw-free cubic graphs. Call such lengths compatible, and let S32 be the set of compatible lengths at most 32. We prove, with computer assistance, that every nonempty finite simple cubic graph of order less than 2182 contains a cycle whose length lies in S32. A second proof, which requires much less computation, gives the same conclusion for graphs of order less than 1504. The argument bounds the size of a breadth-first-search ball. Short cycles are grouped into clusters, of which there are 46 isomorphism types, and the effect of longer cycles is charged to local configurations whose total charge is bounded by exhaustive enumeration and integer optimization. As a consequence, every nonempty finite simple cubic claw-free graph of order less than 6546 contains a cycle whose length is a power of two not exceeding 64.

Authors

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-11-16
DOI
https://doi.org/10.5281/zenodo.24267486
Primary Topic
Limits and Structures in Graph Theory
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Compatible cycles in cubic graphs of small order

Yuta110972
3 links
Zenodo (CERN European Organization for Nuclear Research)
Limits and Structures in Graph Theory
preprint

Compatible cycles in cubic graphs of small order

Yuta110972
preprint en

Abstract

Salehi Nowbandegani, Esfandiari, Shirdareh Haghighi and Bibak conjectured that every cubic graph contains a cycle of some length ℓ for which the interval [2ℓ, 3ℓ] contains a power of two; by contracting triangles, this would imply the Erdős–Gyárfás conjecture for claw-free cubic graphs. Call such lengths compatible, and let S32 be the set of compatible lengths at most 32. We prove, with computer assistance, that every nonempty finite simple cubic graph of order less than 2182 contains a cycle whose length lies in S32. A second proof, which requires much less computation, gives the same conclusion for graphs of order less than 1504. The argument bounds the size of a breadth-first-search ball. Short cycles are grouped into clusters, of which there are 46 isomorphism types, and the effect of longer cycles is charged to local configurations whose total charge is bounded by exhaustive enumeration and integer optimization. As a consequence, every nonempty finite simple cubic claw-free graph of order less than 6546 contains a cycle whose length is a power of two not exceeding 64.

Zenodo (CERN European Organization for Nuclear Research)
Limits and Structures in Graph Theory
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon