A note on hamiltonian cycles in $4$-tough $(P_2\cup k{P}_1)$-free graphs

Abstract

Let $t>0$ be a real number and $G$ be a graph. We say $G$ is $t$-tough if for every cutset $S$ of $G$, the ratio of $|S|$ to the number of components of $G-S$ is at least $t$. The Toughness Conjecture of Chvátal, stating that there exists a constant $t_0$ such that every $t_0$-tough graph with at least three vertices is hamiltonian, is still open in general. For any given integer $k\ge 1$, a graph $G$ is $(P_2\cup k{P}_1)$ free if $G$ does not contain the disjoint union of $P_2$ and $k$ isolated vertices as an induced subgraph. In this note, we show that every 4-tough and $2k$-connected $(P_2\cup k{P}_1)$-free graph with at least three vertices is hamiltonian. This result in some sense is an "extension" of the classical Chvátal-Erdős Theorem that every $\max \{2,k\}$-connected $(k+1)P_1$-free graph on at least three vertices is hamiltonian.

6 pages