Sufficient conditions for $(K_2\cup k{K}_1)$-free graphs to be Hamilton-connected

Abstract

The toughness of a non-complete graph $G$, denoted $\tau (G)$, is defined as \[ τ(G) = \min\left\{ \frac{|S|}{ω(G-S)} : S \subseteq V(G),\ ω(G-S) \geq 2 \right\}, \] where $\omega (G-S)$ is the number of components of $G-S$. For a complete graph $G$, we define $\tau (G)=\infty$. A graph $G$ is $t$-tough if $\tau (G)\ge t$. For a positive integer $k$, a graph $G$ is $(K_2\cup k{K}_1)$-free if it contains no induced subgraph isomorphic to $K_2\cup k{K}_1$. Recently, Liu \cite{liu} showed that every $2k$-connected $(K_2\cup k{K}_1)$-free graph $G$ with $\tau (G)>1$ is Hamilton-connected. In this paper, we strengthen this result by proving that every $(k+1)$-connected $(K_2\cup k{K}_1)$-free graph $G$ with $\tau (G)>1$ and minimum degree $\delta (G)\ge 2k$ is Hamilton-connected. Moreover, by imposing restrictions to the independence number $\alpha (G)$, we prove that every $k$-connected $(K_2\cup k{K}_1)$-free graph $G$ of order $n$ with $2k+1\le \alpha (G)<\frac{n}{2}$ and $\delta (G)\ge 2k$ is Hamilton-connected, and that the bounds on $\alpha (G)$ are sharp.