Hamiltonicity conjecture for subgraphs of powers of paths

Let PnkP_n^k be the kk-th power of the path on nn vertices, and let degG(v)\deg_G(v) denote the degree of vv in GG. Hamiltonicity conjecture for path powers. Let n4n\geq4 and k2k\geq2 be integers. If GPnkG\subseteq P_n^k satisfies

degG(v)degPnk(v)/2+2\deg_G(v)\geq \deg_{P_n^k}(v)/2+2

for every vertex vv, then GG is Hamiltonian. Motivated by the paper's result for effective minimum degree, this conjecture asks whether preserving slightly more than half the degree of every vertex of a path power guarantees a Hamilton cycle; it would imply the one-dimensional case of the cited random-geometric-graph conjecture and remains open in the source.

Sources & referencesView supporting material

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).

Additional references

2 papers in this index state this conjecture (2024). The statement above is taken from the most recent of them; the others are arXiv:2406.09921.

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.