A note on Hamiltonian cycles in 4-tough \((P_2 \cup KP_1)\)-free graphs (Q2675842): Difference between revisions

A graph \(G\) is \(t\)-tough if for every cutset \(S\) of \(G\), the ratio of \(|S|\) to the number of components of \(G-S\) is at least \(t\). \textit{V. Chvátal}'s famous toughness conjecture [ibid. 5, 215--228 (1973; Zbl 0256.05122)], which is still open, states that there exists a constant \(t_0\) such that every \(t_0\)-tough graph is Hamiltonian. There have been a lot of results verifying the conjecture for graphs in which certain small line forests (forests formed from the disjoint union of paths) are forbidden. One such kind of result is on \((P_2 \cup kP_1)\)-free graphs. While there exist results for \(k\in \{1,2,3\}\), the authors investigate the conjecture on \((P_2 \cup kP_1)\)-free graphs with \(k\ge 4\) and obtain general results in this paper. The main result is that for an integer \(k\ge 4\), a \(4\)-tough and \(2k\)-connected \((P_2 \cup kP_1)\)-free graph \(G\) is Hamiltonian. As a corollary, it is also proved that for an integer \(k\ge 4\), every \(k\)-tough \((P_2 \cup kP_1)\)-free graph on at least three vertices is Hamiltonian. The authors also pose a conjecture that the \(4\)-toughness condition in the main result can be reduced to \(1\)-toughness.