PreprintCC BY 4.0arXiv
An Improved Bound for Smith's Longest Cycles Conjecture via a Forbidden Subdivision
Abstract
Smith's conjecture asserts that in every k-connected graph with k≥ 2, any two longest cycles intersect in at least k vertices. In this work, we establish an Ω(k8/11) bound for this conjecture, improving upon the Ω(k2/3) bound of Ma and Zhao. Our proof combines a Ramsey theoretic refinement of the traditional Turán-type approach with computer search.
Related
- An improved bound for the intersection of two longest cycles in k-connected graphs
- Longest cycles intersect linearly in highly connected graphs
- On Chen's conjecture for the log-concavity of the longest increasing subsequence distribution
- Characterization of graphs attaining the maximum signless Laplacian spectral radius under forbidden cycles and theta graphs
- Improved bounds for the two-point logarithmic Chowla conjecture
BibTeX
@misc{chen2026improved,
title = {{An Improved Bound for Smith's Longest Cycles Conjecture via a Forbidden Subdivision}},
author = {Douglas M. Chen},
howpublished = {arXiv},
year = {2026},
month = aug,
doi = {10.48550/arxiv.2608.30353},
eprint = {2608.30353},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.30353},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - An Improved Bound for Smith's Longest Cycles Conjecture via a Forbidden Subdivision
AU - Douglas M. Chen
PY - 2026
DA - 2026/08/31
PB - arXiv
DO - 10.48550/arxiv.2608.30353
UR - https://arxiv.org/abs/2608.30353
AB - Smith's conjecture asserts that in every k-connected graph with k≥ 2, any two longest cycles intersect in at least k vertices. In this work, we establish an Ω(k^8/11) bound for this conjecture, improving upon the Ω(k^2/3) bound of Ma and Zhao. Our proof combines a Ramsey theoretic refinement of the traditional Turán-type approach with computer search.
ER -