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\ge 2$, any two longest cycles intersect in at least $k$ vertices. In this work, we establish an $\Omega (k^{8/11})$ bound for this conjecture, improving upon the $\Omega (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.

9 pages, 2 figures. Comments welcome!