Linear circumference in vertex-transitive graphs
We prove that there is an absolute constant $c>0$ such that every connected vertex-transitive graph $G$ on $n \ge 3$ vertices contains a cycle of length at least $cn$. Moreover, every such graph with sufficiently large degree $d$ contains a cycle of length at least $(1-d^{-1/100})n$. This gives the first linear bound towards Lovász's Hamiltonicity conjecture. The proof combines a structural result of DeVos and Mohar on vertex-transitive graphs with a general framework for finding long cycles, which may be of independent interest.
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.02053
curl -X POST /api/v1/records/arxiv/2610.02053/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.02053/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'