Long Directed Cycles in Vertex-Transitive Digraphs

Abstract

The search for Hamiltonian cycles in vertex-transitive graphs and digraphs is a classical problem at the interface of graph theory and group theory. In the undirected setting, this goes back to the well-known conjectures of Lovász and Thomassen concerning Hamiltonian paths and cycles in connected vertex-transitive graphs. Dating back to Rankin's 1946 work, the directed analogue has an even longer history, linking the search for long cycles to classical group-rearrangement problems. Trotter and Erdős showed in 1978 that connected vertex-transitive digraphs need not be Hamiltonian. In light of this result, Alspach asked in 1981 whether there exist connected vertex-transitive digraphs whose longest directed cycle misses arbitrarily many vertices. This question was only recently resolved by Bucić, Hendrey, Mohar, Steiner and Yepremyan, who constructed connected vertex-transitive digraphs on $n$ vertices whose longest directed cycle omits $(1-o(1))\log n$ vertices. They conjectured that the number of omitted vertices can grow linearly with $n$, remarking that it would already be interesting to improve their logarithmic lower bound to a polynomial bound. In this paper, we confirm their conjecture in a strong form by constructing infinitely many connected vertex-transitive digraphs on $n$ vertices whose longest directed cycle omits at least $n/12$ vertices. In the same work, Bucić, Hendrey, Mohar, Steiner and Yepremyan also proved that every connected vertex-transitive digraph on $n$ vertices contains a directed cycle of length $Ω(n^{1/3})$, giving the first lower bound for this problem that grows with $n$. We improve this to $Ω(\sqrt n)$, matching the order of Babai's classical theorem from 1979 for undirected vertex-transitive graphs.

Disclosure

“infinitely many values of n, namely for all multiples of 12. □ Acknowledgements We are grateful to Matija Bucić and Shoham Letzter for helpful discussions on the Lovász conjecture. OpenAI Codex (GPT-5.6 Sol) was used to assist with proofreading this paper. All mathematical ideas and arguments are entirely due to the authors, who take full responsibility for the content. Refere”

PDF page 13

Classification

Proofreading, grammar, or spelling

Multiplier

1

Verified

2026-08-24T00:34:09.244Z

Structural counts