Some conditions for hamiltonian cycles in 1-tough $(K_2\cup k{K}_1)$-free graphs

Abstract

Let $k\ge 2$ be an integer. We say that a graph $G$ is $(K_2\cup k{K}_1)$-free if it does not contain $K_2\cup k{K}_1$ as an induced subgraph. Recently, Shi and Shan conjectured that every $1$-tough and $2k$-connected $(K_2\cup k{K}_1)$-free graph is hamiltonian. In this paper, we solve this conjecture by proving the statement; every $1$-tough and $k$-connected $(K_2\cup k{K}_1)$-free graph with minimum degree at least $\frac{3(k-1)}{2}$ is hamiltonian or the Petersen graph.

11 pages, 1 figure