Induced nets and Hamiltonicity of claw-free graphs

2018/03/26 by Shuya Chiba, Chiba, Shuya, Jun Fujisawa +1
Mathematics · #05C38 #05C45 #05C75 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C38 #msc:05C45 #msc:05C75

paper · pdf · doi:10.48550/arxiv.1803.09416

19 pages, 5 figures

arxiv created 2018/03/26 · arxiv updated 2018/03/28

Abstract

The connected graph of degree sequence 3,3,3,1,1,1 is called a net, and the vertices of degree 1 in a net is called its endvertices. Broersma conjectured in 1993 that a 2-connected graph G with no induced K_1,3 is hamiltonian if every endvertex of each induced net of G has degree at least (|V(G)|-2)/3. In this paper we prove this conjecture in the affirmative.

Related

• A supplement to "Induced nets and Hamiltonicity of claw-free graphs"
• On Hamiltonicity of claw, net-free graphs
• Proof of a conjecture on hamiltonian-connected graphs
• Forcing Hamiltonicity in locally finite graphs via forbidden induced subgraphs I: nets and bulls
• Disconnected Forbidden Subgraphs, Toughness and Hamilton Cycles