Connected vertex-transitive digraphs on n vertices can have perimeter gap ≥ n/12, and every such digraph contains a directed cycle of length Ω(√n).
Longer cycles in vertex transitive graphs
2 Pith papers cite this work. Polarity classification is still indexing.
2
Pith papers citing it
abstract
In 1979 Babai found a clever argument to prove that every connected vertex transitive graph on $n \ge 3$ vertices contains a cycle of length at least $\sqrt{3n}$. Here we modify his approach to show that such graphs must contain a cycle of length at least $(1 - o(1))n^{3/5}$.
fields
math.CO 2years
2026 2representative citing papers
Every connected vertex-transitive graph of order n contains a cycle of length at least n^(2/3-o(1)), up from the previous n^(9/14).
citing papers explorer
-
Long Directed Cycles in Vertex-Transitive Digraphs
Connected vertex-transitive digraphs on n vertices can have perimeter gap ≥ n/12, and every such digraph contains a directed cycle of length Ω(√n).
-
Towards the Lov\'{a}sz conjecture via sublinear expanders
Every connected vertex-transitive graph of order n contains a cycle of length at least n^(2/3-o(1)), up from the previous n^(9/14).