Verstraëte's minimum-degree conjecture on cycle lengths in Hamiltonian graphs

At least 4 years old · documented by

Let GG be an nn-vertex Hamiltonian graph, and let δ(G)\delta(G) denote its minimum degree. Verstraëte's conjecture. If

δ(G)≥3,\delta(G)\geq 3,

then GG has Ω(n)\Omega(n) different cycle lengths. This strengthens the Jacobson–Lehel question by replacing regularity with a minimum-degree condition. The paper proves the asymptotic lower bound n1−o(1)n^{1-o(1)}, but the asserted linear bound remains open.

References

Primary source

Matija Bucić, Lior Gishboliner and Benny Sudakov, “Cycles of many lengths in Hamiltonian graphs”, arXiv:2104.07633 (2021).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.