Skip to content
DraconiticResearch
Search Sources API
210,423 studies31 sourcesUpdated 50 min ago
PreprintarXiv licencearXiv

Longest cycles and Dirac-type results in highly connected graphs

  • Jie Ma
  • Bo Ning
  • Ziyuan Zhao
Open at sourcePDFDOICite

Abstract

A classical theorem of Nash-Williams states that if G is a $2$-connected graph on n vertices with minimum degree at least (n+2)/3, then for every longest cycle C of G, the graph G−V(C) is edgeless. Motivated by a higher-connectivity analogue, Bondy conjectured in 1980 that if G is a k-connected graph on n vertices with minimum degree at least (n+k(k−1))/(k+1), then for every longest cycle C of G, every path in G−V(C) has at most k−1 vertices. This conjecture is known for k≤ 3 and remains open for all k≥ 4. In this paper, we prove Bondy's conjecture for all sufficiently large graphs. The key ingredient is a new Dirac-type theorem that gives a lower bound on the length of a longest cycle in a k-connected graph, which also yields a partial solution to a conjecture of Jung from 1990. Along the way, we develop several new tools, including a DFS lemma and an average-degree analogue of the Bondy--Jackson theorem. We conclude with a discussion of related problems and a counterexample to a conjecture of Voss from 1991.

Versions

Related

  1. Longest cycles intersect linearly in highly connected graphs
    Jie Ma, Bo Ning, Ziyuan Zhao
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. An improved bound for the intersection of two longest cycles in k-connected graphs
    Juan Gutiérrez
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  3. On Hamilton cycles in connected vertex-transitive graphs of order 2pq
    Zhou Tianlei
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. Modulo k-orientations of highly edge-connected signed graphs
    You Lu, Zhengke Miao, Zhenyu Tian +1
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. 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

Cite

BibTeXRIS
BibTeX
@misc{ma2026longest,
  title = {{Longest cycles and Dirac-type results in highly connected graphs}},
  author = {Jie Ma and Bo Ning and Ziyuan Zhao},
  howpublished = {arXiv},
  year = {2026},
  month = jun,
  doi = {10.48550/arxiv.2606.03696},
  eprint = {2606.03696},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2606.03696},
}
RIS
TY  - UNPB
TI  - Longest cycles and Dirac-type results in highly connected graphs
AU  - Jie Ma
AU  - Bo Ning
AU  - Ziyuan Zhao
PY  - 2026
DA  - 2026/06/02
PB  - arXiv
DO  - 10.48550/arxiv.2606.03696
UR  - https://arxiv.org/abs/2606.03696
AB  - A classical theorem of Nash-Williams states that if G is a $2$-connected graph on n vertices with minimum degree at least (n+2)/3, then for every longest cycle C of G, the graph G−V(C) is edgeless. Motivated by a higher-connectivity analogue, Bondy conjectured in 1980 that if G is a k-connected graph on n vertices with minimum degree at least (n+k(k−1))/(k+1), then for every longest cycle C of G, every path in G−V(C) has at most k−1 vertices. This conjecture is known for k≤ 3 and remains open for all k≥ 4. In this paper, we prove Bondy's conjecture for all sufficiently large graphs. The key ingredient is a new Dirac-type theorem that gives a lower bound on the length of a longest cycle in a k-connected graph, which also yields a partial solution to a conjecture of Jung from 1990. Along the way, we develop several new tools, including a DFS lemma and an average-degree analogue of the Bondy--Jackson theorem. We conclude with a discussion of related problems and a counterexample to a conjecture of Voss from 1991.
ER  -