The Chvátal-Erdős condition for prism-Hamiltonicity

Abstract

The prism over a graph $G$ is the cartesian product $G\square K_2$. It is known that the property of having a Hamiltonian prism (prism-Hamiltonicity) is stronger than that of having a $2$-walk (spanning closed walk using every vertex at most twice) and weaker than that of having a Hamilton path. For a graph $G$, it is known that $\alpha (G)\le 2\kappa (G)$, where $\alpha (G)$ is the independence number and $\kappa (G)$ is the connectivity, imples existence of a $2$-walk in $G$, and the bound is sharp. West asked for a bound on $\alpha (G)$ in terms of $\kappa (G)$ guaranteeing prism-Hamiltonicity. In this paper we answer this question and prove that $\alpha (G)\le 2\kappa (G)$ implies the stronger condition, prism-Hamiltonicity of $G$.

7 pages, no figures