{"id":"arxiv/2605.19508","url":"https://arxiv.org/abs/2605.19508","tags":["math.CO"],"score":0,"title":"On hamiltonian cycles of 1-tough $(P_{2} \\cup kP_{1})$-free graphs","domain":"math.CO","source":"arxiv","authors":["Masahiro Sanka"],"reviews":0,"subject":"math.CO","summary":"Let $k$ be a positive integer. A graph is said to be $(P_2 \\cup kP_1)$-free if it does not contain $P_2 \\cup kP_1$ as an induced subgraph. Recently, Ota and the author asked whether every 1-tough and $k$-connected $(P_2 \\cup kP_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 \\geq 4$, if $G$ is a $1$-tough and $(k-1)$-connected $(P_2 \\cup kP_1)$-free graph with $|V(G)| \\ge k^2+k+1$ and $δ(G) \\ge k$, then $G$ is hamiltonian. This result implies that the above…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-05-19","reactions":{}}