Kaiser et al.'s prism-toughness conjecture
Kaiser et al.'s prism-toughness conjecture
Let be a simple finite graph. The prism over is the Cartesian product
A graph is prism-hamiltonian when its prism is hamiltonian. Call -tough if for every with .
Kaiser et al.'s prism-toughness conjecture. There exists a constant such that the prism over any -tough graph is hamiltonian.
Hamiltonian paths imply prism-hamiltonicity, which implies the existence of a spanning -walk, but neither implication reverses in general. The conjecture asks whether a universal toughness threshold guarantees prism-hamiltonicity and remains open.
Sources & referencesView supporting material
Primary source
M. N. Ellingham, Pouria Salehi Nowbandegani and Songling Shan, “Toughness and prism-hamiltonicity of P_4-free graphs”, arXiv:1901.01959 (2019).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.