Hamiltonian cycles in tough \((P_2\cup P_3)\)-free graphs (Q2227834): Difference between revisions

Summary: Let \(t>0\) be a real number and \(G\) be a graph. We say \(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\). Determining toughness is an NP-hard problem for arbitrary graphs. The Toughness Conjecture of Chvátal, stating that there exists a constant \(t_0\) such that every \(t_0\)-tough graph with at least three vertices is hamiltonian, is still open in general. A graph is called \((P_2\cup P_3)\)-free if it does not contain any induced subgraph isomorphic to \(P_2\cup P_3\), the union of two vertex-disjoint paths of order 2 and 3, respectively. In this paper, we show that every 15-tough \((P_2\cup P_3)\)-free graph with at least three vertices is hamiltonian.