Hamilton cycles in tough (2P₂ ∪ P₁)-free graphs

2025/06/15 by Songling Shan, Shan, Songling, Arthur Tanyel +1
Engineering · Mathematics · Computer Science · #graph theory and CDMA systems #Limits and Structures in Graph Theory #Advanced Graph Theory Research

paper · pdf · doi:10.48550/arxiv.2506.12684

Abstract

In 1973, Chvátal conjectured that there exists a constant t₀ such that every t₀-tough graph on at least three vertices is Hamiltonian. While this conjecture is still open, work has been done to confirm it for several graph classes, including all F-free graphs for every 5-vertex linear forest F other than P₅ and 2P₂∪ P₁. In this note, we show that 11-tough (2P₂ ∪ P₁)-free graphs on at least three vertices are Hamiltonian.

Related

• Hamiltonian cycles in tough (P₄ ∪ P₁)-free graphs
• Hamiltonian cycles in 7-tough (P₃∪ 2P₁)-free graphs
• A note on hamiltonian cycles in 4-tough (P₂∪ kP₁)-free graphs
• Hamiltonian cycles in 15 -tough ( P₃∪ 3P₁ )-free graphs
• Hamiltonicity of 1-tough (P₂∪ kP₁)-free graphs