























The prism over a graph $G$ is the cartesian product $G \Box 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 $α(G) \leq 2 κ(G)$, where $α(G)$ is the independence number and $κ(G)$ is the connectivity, imples existence of a $2$-walk in $G$, and the bound is sharp. West asked for a bound on $α(G)$ in terms of $κ(G)$ guaranteeing prism-Hamiltonicity. In this paper we answer this question and prove that $α(G) \leq 2 κ(G)$ implies the stronger condition, prism-Hamiltonicity of $G$.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。