ELW's Hamiltonicity conjecture for subgraphs of powers of cycles

About 2 years old · traced to

Let CnkC_n^k be the kk-th power of the cycle on nn vertices, and let δ(G)\delta(G) denote the minimum degree of a graph GG. ELW's Hamiltonicity conjecture. For all integers n≥3n\geq3 and k∈[1,n/2]k\in [1,n/2], every graph G⊆CnkG\subseteq C_n^k with δ(G)≥k+1\delta(G)\geq k+1 is Hamiltonian. This conjecture concerns a sufficient minimum-degree condition for subgraphs of powers of cycles to contain a Hamilton cycle and arises from the study of local resilience in random geometric graphs; its resolution is not given here.

References

Primary source

Alberto Espuny Díaz, Pranshu Gupta, Domenico Mergoni Cecchelli, Olaf Parczyk and Amedeo Sgueglia, “Dirac's theorem for graphs of bounded bandwidth”, arXiv:2407.05889 (2024).

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.