Longest cycles in vertex-transitive and highly connected graphs
<|reference_start|>Longest cycles in vertex-transitive and highly connected graphs: We present progress on two old conjectures about longest cycles in graphs. The first conjecture, due to Thomassen from 1978, states that apart from a finite number of exceptions, all connected vertex-transitive graphs contain a Hamiltonian cycle. The second conjecture, due to Smith from 1984, states that for $r\ge 2$ in every $r$-connected graph any two longest cycles intersect in at least $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 towards both of the aforementioned conjectures: First, we show that every connected vertex-transitive graph on $n\geq 3$ vertices contains a cycle of length at least $\Omega(n^{13/21})$, improving on $\Omega(n^{3/5})$ from [De Vos, arXiv:2302:04255, 2023]. Second, we show that in every $r$-connected graph with $r\geq 2$, any two longest cycles meet in at least $\Omega(r^{5/8})$ vertices, improving on $\Omega(r^{3/5})$ from [Chen, Faudree and Gould, J. Combin. Theory, Ser.~ B, 1998]. Our proof combines combinatorial arguments, computer-search and linear programming.<|reference_end|>
@article{groenland2024longest,
    title={Longest cycles in vertex-transitive and highly connected graphs},
    author={Carla Groenland, Sean Longbrake, Raphael Steiner, J'er'emie
  Turcotte, Liana Yepremyan},
    journal={arXiv preprint arXiv:2408.04618},
    year={2024},
    archivePrefix={arXiv},
    eprint={2408.04618},
    primaryClass={math.CO cs.DM}
}