Skip to content
DraconiticResearch
Search Sources API
203,203 studies31 sourcesUpdated 3 min ago
Peer-reviewedCC BYJournal of the European Mathematical Society

Pancyclicity of highly connected graphs

  • Shoham Letzter1
  1. 1University College London, UK
Open at sourceDOICite

Abstract

A well-known result due to Chvátal and Erdős (1972) asserts that, if a graph G satisfies \kappa(G) \ge \alpha(G) , where \kappa(G) is the vertex-connectivity of G , then G has a Hamilton cycle. We prove a similar result implying that a graph G is pancyclic , that is, it contains cycles of all lengths between 3 and |G| : if |G| is large and \kappa(G) > \alpha(G) , then G is pancyclic. This confirms a conjecture of Jackson and Ordaz (1990) for large graphs, and improves upon a very recent result of Draganić, Munhá Correia, and Sudakov.

Related

  1. Modulo k-orientations of highly edge-connected signed graphs
    You Lu, Zhengke Miao, Zhenyu Tian +1
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. Longest cycles intersect linearly in highly connected graphs
    Jie Ma, Bo Ning, Ziyuan Zhao
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. A note on highly connected K2,ℓ -minor free graphs
    Nicolas Bousquet, Théo Pierron, Alexandra Wesolek
    Discrete MathematicsPeer-reviewedCC BY 4.0Full textCombinatorics & discrete mathematicsHAL
  4. Hitting Maximum Independent Sets in Dense and Highly Connected Graphs
    Hanzhi Bai, Yufei Chang, Jin Yan
    arXivPreprintCC0Full textCombinatorics & discrete mathematicsarXiv
  5. Sharp connectivity thresholds for mixed rigidity packings and improved bounds for highly connected orientations of graphs
    Hanzhi Bai, Jørgen Bang-Jensen, Jin Yan
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@article{letzter2026pancyclicity,
  title = {{Pancyclicity of highly connected graphs}},
  author = {Shoham Letzter},
  journal = {Journal of the European Mathematical Society},
  year = {2026},
  month = jul,
  doi = {10.4171/jems/1808},
  url = {https://doi.org/10.4171/jems/1808},
  note = {CC BY},
}
RIS
TY  - JOUR
TI  - Pancyclicity of highly connected graphs
AU  - Shoham Letzter
PY  - 2026
DA  - 2026/07/28
JO  - Journal of the European Mathematical Society
DO  - 10.4171/jems/1808
UR  - https://doi.org/10.4171/jems/1808
AB  - A well-known result due to Chvátal and Erdős (1972) asserts that, if a graph G satisfies \kappa(G) \ge \alpha(G) , where \kappa(G) is the vertex-connectivity of G , then G has a Hamilton cycle. We prove a similar result implying that a graph G is pancyclic , that is, it contains cycles of all lengths between 3 and |G| : if |G| is large and \kappa(G) > \alpha(G) , then G is pancyclic. This confirms a conjecture of Jackson and Ordaz (1990) for large graphs, and improves upon a very recent result of Draganić, Munhá Correia, and Sudakov.
SN  - 1435-9855
SN  - 1435-9863
ER  -