The Existence of a 2-Factor in a Graph Satisfying the Local Chvátal--Erdös Condition
Guantao Chen, Akira Saito, Songling Shan · SIAM Journal on Discrete Mathematics · 2013
The well-known Chvátal--Erdös theorem states that every graph $G$ of order at least three with $\alpha(G)\le\kappa(G)$ has a Hamiltonian cycle, where $\alpha(G)$ and $\kappa(G)$ are the independence number and the connectivity of $G$, respectively. Oberly and Sumner [J. Graph Theory, 3 (1979), pp. 351--356] have proved that every connected, locally connected claw-free graph of order at least three has a Hamiltonian cycle. We study the connection of these two theorems. For $x\in V(G)$, let $B(x)$ denote the subgraph of $G$ induced by the closed neighborhood of $x$. Then the theorem by Oberly and Sumner says that a connected graph $G$ of order at least three satisfying $\alpha(B(x))\le 2\le \kappa(B(x))$ for every vertex $x$ has a Hamiltonian cycle. The comparison of this theorem with the Chvátal--Erdös theorem leads us to suspect that the threshold 2 between $\alpha(B(x))$ and $\kappa(B(x))$ is not necessary. We say that $G$ satisfies the local Chvátal--Erdös condition if $\alpha(B(x))\le\kappa(B(x))$ holds for every vertex $x$ in $G$. The second author conjectured that if the order of a connected graph $G$ is at least three and satisfies the local Chvátal--Erdös condition, then $G$ has a Hamiltonian cycle. In this paper, we support this conjecture by proving that under this assumption, $G$ is $1$-tough and has a $2$-factor.