PreprintarXiv licencearXiv
Linear circumference in vertex-transitive graphs
Abstract
We prove that there is an absolute constant c>0 such that every connected vertex-transitive graph G on n ≥ 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.
Related
- Multi-Way Expansion, Laplacian Gaps, and Imprimitivity in Vertex-Transitive Graphs
- Vertex-transitive strongly regular graphs in the switching class of doubly transitive two-graphs
- Enumeration of small vertex-transitive directed strongly regular graphs
- Counting Minimal Vertex Cutsets and a Gap at 1 for Site Percolation on Vertex-Transitive Graphs
- Vertex-transitive quantum graphs
BibTeX
@misc{ma2026linear,
title = {{Linear circumference in vertex-transitive graphs}},
author = {Jie Ma and Ziyuan Zhao},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.02053},
eprint = {2610.02053},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.02053},
}
RIS
TY - UNPB
TI - Linear circumference in vertex-transitive graphs
AU - Jie Ma
AU - Ziyuan Zhao
PY - 2026
DA - 2026/10/01
PB - arXiv
DO - 10.48550/arxiv.2610.02053
UR - https://arxiv.org/abs/2610.02053
AB - We prove that there is an absolute constant c>0 such that every connected vertex-transitive graph G on n ≥ 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.
ER -