PreprintCC BY 4.0arXiv
An improved bound for the intersection of two longest cycles in k-connected graphs
Abstract
A conjecture attributed to Smith states that in every k-connected graph, every pair of longest cycles intersects in at least k vertices. We prove that every two longest cycles in a k-connected graph on n vertices intersect in at least min{k,10k−n−30} vertices. Consequently, Smith's conjecture holds whenever k≥ (n+30)/9. This improves the previous bound of (n+16)/7 for n>33 and also implies a bound of (n+22)/9 for paths instead of cycles.
Related
- Longest cycles intersect linearly in highly 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
- Long Cycles in 2-Connected Tough Graphs
- Sharp connectivity thresholds for mixed rigidity packings and improved bounds for highly connected orientations of graphs
BibTeX
@misc{gutierrez2026improved,
title = {{An improved bound for the intersection of two longest cycles in $k$-connected graphs}},
author = {Juan Gutiérrez},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.07145},
eprint = {2611.07145},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.07145},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - An improved bound for the intersection of two longest cycles in k-connected graphs
AU - Juan Gutiérrez
PY - 2026
DA - 2026/11/04
PB - arXiv
DO - 10.48550/arxiv.2611.07145
UR - https://arxiv.org/abs/2611.07145
AB - A conjecture attributed to Smith states that in every k-connected graph, every pair of longest cycles intersects in at least k vertices. We prove that every two longest cycles in a k-connected graph on n vertices intersect in at least min{k,10k−n−30} vertices. Consequently, Smith's conjecture holds whenever k≥ (n+30)/9. This improves the previous bound of (n+16)/7 for n>33 and also implies a bound of (n+22)/9 for paths instead of cycles.
ER -