A graph $ G $ is called $ t $-tough if $ \left|S\right|\geq t\cdot w\left(G-S\right)$ for every cutset $ S $ of $G$. Chv\'atal conjectured that there exists a constant $ t_{ 0} $ such that every $ t_{ 0} $-tough graph has a hamiltonian cycle. Gao and Shan have proved that every $7$-tough $(P_{ 3}\cup 2P_{ 1})$-free grah is hamiltonian. In this paper, we confirm this conjecture for $ (P_{ 3}\cup 3P_{ 1}) $-free graphs.

Categories: math.CO

Hamiltonian cycles in $ 15 $-tough ($ P_{3}\cup 3P_{1} $)-free graphs