Hamiltonian cycles in 7-tough (P₄∪ P₁)-free graphs

2026/07/22 by Yong Lu, Qi Wu, Qiannan Zhou
#math.CO

paper · pdf

Abstract

Shan~[J. Graph Theory (2026)] proved that every 23-tough (P₄∪ P₁)-free graph on at least three vertices is Hamiltonian. We improve this bound to 7 by replacing the final cut analysis in Shan's framework with an asymmetric separation criterion and a cograph covering lemma.

Citations

• Some Theorems on Abstract Graphs

Related

• Hamiltonian cycles in tough (P₄ ∪ P₁)-free graphs
• Hamiltonian cycles in 7-tough (P₃∪ 2P₁)-free graphs
• Hamilton cycles in tough (2P₂ ∪ P₁)-free graphs
• Hamiltonian cycles in 3-tough 2K₂-free graphs
• Hamiltonian cycles in 15 -tough ( P₃∪ 3P₁ )-free graphs