pipette
ENEnglish

Linear circumference in vertex-transitive graphs

Jie Ma, Ziyuan Zhao

PreprintDice ser un gran avance

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.