Closure for the property of having a hamiltonian prism
Daniel Král͏̌, Ladislav Stacho · Journal of Graph Theory · 2006
Abstract We prove that a graph G of order n has a hamiltonian prism if and only if the graph Cl4n/3–4/3(G) has a hamiltonian prism where Cl4n/3–4/3(G) is the graph obtained from G by sequential adding edges between non‐adjacent vertices whose degree sum is at least 4n/3–4/3. We show that this cannot be improved to less than 4n/3–5. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 209–220, 2007