Kaiser et al.'s prism-toughness conjecture

Let GG be a simple finite graph. The prism over GG is the Cartesian product

GK2.G\mathbin{\Box}K_2.

A graph is prism-hamiltonian when its prism is hamiltonian. Call GG tt-tough if Stc(GS)|S|\geq t\,c(G-S) for every SV(G)S\subseteq V(G) with c(GS)2c(G-S)\geq 2.

Kaiser et al.'s prism-toughness conjecture. There exists a constant t1t_1 such that the prism over any t1t_1-tough graph is hamiltonian.

Hamiltonian paths imply prism-hamiltonicity, which implies the existence of a spanning 22-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

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.