Every 2k-connected (P₂∪ kP₁)-free graph with toughness greater than one is hamiltonian-connected

2025/03/17 by Liu, Feng
#05C42 #05C45 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2503.12860

Abstract

Given a graph H, a graph G is H-free if G does not contain H as an induced subgraph. Shi and Shan conjectured that every 1-tough 2k-connected (P₂ ∪ kP₁)-free graph is hamiltonian for k ≥ 4. This conjecture has been independently confirmed by Xu, Li, and Zhou, as well as by Ota and Sanka. Inspired by this, we prove that every 2k-connected (P₂∪ kP₁)-free graph with toughness greater than one is hamiltonian-connected.

Related

• Some conditions for hamiltonian cycles in 1-tough (K₂ ∪ kK₁)-free graphs
• Hamiltonicity of 1-tough (P₂∪ kP₁)-free graphs
• Hamiltonian cycles in 2-tough 2K₂-free graphs
• Disconnected Forbidden Subgraphs, Toughness and Hamilton Cycles
• Hamiltonian cycles in 7-tough (P₄∪ P₁)-free graphs