The bounded-defect cycle conjecture for Hamiltonian graphs

Let GG be an nn-vertex graph, and write δ(G)\delta(G) for its minimum degree. A Hamiltonian cycle is a cycle spanning all vertices of GG. The bounded-defect cycle conjecture. If δ(G)3\delta(G)\geq 3 and GG contains a Hamiltonian cycle, then GG contains another cycle of length at least

nK,n-K,

where K>0K>0 is an absolute constant. The conjecture asks whether the error term in the paper's asymptotic result can be bounded independently of nn; the source notes that even K=2K=2 may be possible, while related constructions may rule out such small values.

Sources & referencesView supporting material

Primary source

António Girão, Teeradej Kittipassorn and Bhargav Narayanan, “Long cycles in Hamiltonian graphs”, arXiv:1709.04895 (2017).

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.