Cycles of many lengths in Hamiltonian graphs

Matija Bucić, Lior Gishboliner, Benny Sudakov

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

In 1999, Jacobson and Lehel conjectured that, for Formula Presented, every k-regular Hamiltonian graph has cycles of Formula Presented many different lengths. This was further strengthened by Verstraëte, who asked whether the regularity can be replaced with the weaker condition that the minimum degree is at least Formula Presented. Despite attention from various researchers, until now, the best partial result towards both of these conjectures was a Formula Presented lower bound on the number of cycle lengths. We resolve these conjectures asymptotically by showing that the number of cycle lengths is at least Formula Presented.

Original languageEnglish (US)
Article numbere70
JournalForum of Mathematics, Sigma
Volume10
DOIs
StatePublished - Aug 31 2022

All Science Journal Classification (ASJC) codes

  • Analysis
  • Theoretical Computer Science
  • Algebra and Number Theory
  • Statistics and Probability
  • Mathematical Physics
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Mathematics

Fingerprint

Dive into the research topics of 'Cycles of many lengths in Hamiltonian graphs'. Together they form a unique fingerprint.

Cite this