2025/08/24 by Ma, Jie, Zhao, Ziyuan · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2508.17438
Motivated by the classical conjectures of Lovász, Thomassen, and Smith, recent work has renewed interest in the study of longest cycles in important graph families, such as vertex-transitive and highly connected graphs. In particular, Groenland et al. proved that if two longest cycles and in a graph share m vertices, then there exists a vertex cut of size O(m8/5) separating them, yielding improved bounds toward these conjectures. Their proof combines Turán-type arguments with computer-assisted search. We prove two results addressing problems of Babai (1979) and Smith (1984) on intersections of longest cycles in vertex-transitive and highly connected graphs. First, we strengthen the bound of Groenland et al. by showing that if two longest cycles and in a graph share m vertices, then there exists a vertex cut of size O(m3/2) separating them. As a consequence, we show that in every \(k\)-connected graph, any two longest cycles intersect in at least \(Ω(k2/3)\) vertices, improving the best known bound toward Smith's conjecture. Our proof is purely combinatorial, employing supersaturation-type estimates beyond the existing Turán-type approach. Second, we prove that in every connected vertex-transitive graph on \(n\) vertices, any two longest cycles intersect in at least \(f(n)\) vertices for some function \(f(n)→∞\) as \(n→∞\), thereby resolving a problem of Babai (1979) for the class of vertex-transitive graphs central to his original motivation. In doing so, we introduce a new method for constructing longer cycles in vertex-transitive graphs based on a given cycle, which may be of independent interest.