On hamiltonian cycles of 1-tough $(P_2\cup k{P}_1)$-free graphs

Abstract

Let $k$ be a positive integer. A graph is said to be $(P_2\cup k{P}_1)$-free if it does not contain $P_2\cup k{P}_1$ as an induced subgraph. Recently, Ota and the author asked whether every 1-tough and $k$-connected $(P_2\cup k{P}_1)$-free graph is hamiltonian or the Petersen graph. Note that this problem is affirmative for $k\in \{1,2,3\}$ by the known results. In this paper, we show that for each integer $k\ge 4$, if $G$ is a $1$-tough and $(k-1)$-connected $(P_2\cup k{P}_1)$-free graph with $|V(G)|\ge k^2+k+1$ and $\delta (G)\ge k$, then $G$ is hamiltonian. This result implies that the above question is affirmative for large graphs.

11 pages, 1 figure