Proof of a conjecture on hamiltonian-connected graphs

2021/10/29 by Petr Vrána, Vrana, Petr, Xingzhi Zhan +3
Computer Science · Mathematics · #05C38 #05C45 #05C69 #Advanced Graph Theory Research #China #Combinatorics #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Conjecture #Discrete mathematics #FOS: Mathematics #Graph #Graph Labeling and Dimension Problems #Hamiltonian (control theory) #Hamiltonian path #Law #Mathematics #Political science #Zhàng

paper · pdf · doi:10.48550/arxiv.2110.15519

openalex publication_date 2021/10/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We prove that every 3-connected claw-free graph with domination number at most 3 is hamiltonian-connected. The result is sharp and it is inspired by a conjecture posed by Zheng, Broersma, Wang and Zhang in 2020.

Citations

• Line graphs of multigraphs and Hamilton-connectedness of claw-free graphs

Related

• Every 3-connected \K_1,3,Γ₃\-free graph is Hamilton-connected
• Every 2k-connected (P₂∪ kP₁)-free graph with toughness greater than one is hamiltonian-connected
• Induced nets and Hamiltonicity of claw-free graphs
• Hamiltonicity and structure of connected biclaw-free graphs
• Hamiltonicity of Domination Vertex-Critical Claw-Free Graphs