This is not the latest version of this item. The latest version can be found here.
Longest cycles in vertex-transitive and highly connected graphs
OPEN ACCESS
Loading...
Author / Producer
Date
2025
Publication Type
Journal Article
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
Abstract
We present progress on three old conjectures about longest paths and cycles in graphs. The first pair of conjectures, due to Lov & aacute;sz from 1969 and Thomassen from 1978, respectively, states that all connected vertex-transitive graphs contain a Hamiltonian path, and that all sufficiently large such graphs even contain a Hamiltonian cycle. The third conjecture, due to Smith from 1984, states that for r >= 2$r\geqslant 2$ in every r$r$-connected graph any two longest cycles intersect in at least r$r$ vertices. In this paper, we prove a new lemma about the intersection of longest cycles in a graph, which can be used to improve the best known bounds toward all the aforementioned conjectures: First, we show that every connected vertex-transitive graph on n >= 3$n\geqslant 3$ vertices contains a cycle (and hence path) of length at least Omega(n13/21)$\Omega (n<^>{13/21})$, improving on Omega(n3/5)$\Omega (n<^>{3/5})$ from DeVos [arXiv:2302:04255, 2023]. Second, we show that in every r$r$-connected graph with r >= 2$r\geqslant 2$, any two longest cycles meet in at least Omega(r5/8)$\Omega (r<^>{5/8})$ vertices, improving on Omega(r3/5)$\Omega (r<^>{3/5})$ from Chen, Faudree, and Gould [J. Combin. Theory, Ser. B, 72 (1998) no. 1, 143-149]. Our proof combines combinatorial arguments, computer search, and linear programming.
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
Pages / Article No.
Publisher
Wiley