babylonpolice.com

Given a graph $H$, a graph $G$ is $H$-free if $G$ does not contain $H$ as an
induced subgraph. For a positive real number $t$, a non-complete graph $G$ is
said to be $t$-tough if for every vertex cut $S$ of $G$, the ratio of $|S|$ to
the number of components of $G-S$ is at least $t$. A complete graph is said to
be $t$-tough for any $t>0$. Chv\'{a}tal's toughness conjecture, 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. Chv\'{a}tal and
Erd\"{o}s \cite{CE} proved that, for any integer $k\ge 1$, every
$\max\{2,k\}$-connected $(k+1)P_1$-free graph on at least three vertices is
Hamiltonian. Along the Chv\'{a}tal-Erd\"{o}s theorem, Shi and Shan \cite{SS}
proved that, for any integer $k\ge 4$, every $4$-tough $2k$-connected $(P_2\cup
kP_1)$-free graph with at least three vertices is Hamiltonian, and furthermore,
they proposed a conjecture that for any integer $k\ge 1$, any $1$-tough
$2k$-connected $(P_2\cup kP_1)$-free graph is Hamiltonian. In this paper, we
confirm the conjecture, and furthermore, we show that if $k\ge 3$, then the
condition `$2k$-connected' may be weakened to be `$2(k-1)$-connected'. As an
immediate consequence, for any integer $k\ge 3$, every $(k-1)$-tough $(P_2\cup
kP_1)$-free graph is Hamiltonian. This improves the result of Hatfield and
Grimm \cite{HG}, stating that every $3$-tough $(P_2\cup 3P_1)$-free graph is
Hamiltonian.