PreprintarXiv licencearXiv
Longest cycles intersect linearly in highly connected graphs
Abstract
A longstanding conjecture attributed to Smith (1984) asserts that for every k≥2, any two longest cycles in a k-connected graph share at least k vertices. In this paper, we prove the first linear lower bound, showing that any two longest cycles in a k-connected graph share at least k/600 vertices. Departing from previous Turán-type extremal arguments, we develop a novel structural approach that also yields applications to related problems on longest cycles and paths.
Related
- An improved bound for the intersection of two longest cycles in k-connected graphs
- An Improved Bound for Smith's Longest Cycles Conjecture via a Forbidden Subdivision
- On Hamilton cycles in connected vertex-transitive graphs of order 2pq
- Highly connected uniquely k-linked digraphs
- Long Cycles in 2-Connected Tough Graphs
BibTeX
@misc{ma2026longest,
title = {{Longest cycles intersect linearly in highly connected graphs}},
author = {Jie Ma and Bo Ning and Ziyuan Zhao},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.20724},
eprint = {2609.20724},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.20724},
}
RIS
TY - UNPB
TI - Longest cycles intersect linearly in highly connected graphs
AU - Jie Ma
AU - Bo Ning
AU - Ziyuan Zhao
PY - 2026
DA - 2026/09/17
PB - arXiv
DO - 10.48550/arxiv.2609.20724
UR - https://arxiv.org/abs/2609.20724
AB - A longstanding conjecture attributed to Smith (1984) asserts that for every k≥2, any two longest cycles in a k-connected graph share at least k vertices. In this paper, we prove the first linear lower bound, showing that any two longest cycles in a k-connected graph share at least k/600 vertices. Departing from previous Turán-type extremal arguments, we develop a novel structural approach that also yields applications to related problems on longest cycles and paths.
ER -