Linear circumference in vertex-transitive graphs
En palabras de los autores
We prove that there is an absolute constant such that every connected vertex-transitive graph on vertices contains a cycle of length at least . Moreover, every such graph with sufficiently large degree contains a cycle of length at least . This gives the first linear bound towards Lov\'asz'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.
Resultado principalLimitación que admiten los autores
Apareció: viernes, 2 de octubre. arXiv. Preprint, todavía sin revisión por pares.