Induced Nets and Hamiltonicity of Claw-Free Graphs

Shuya Chiba, Jun Fujisawa

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)


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 are called its endvertices. Broersma conjectured in 1993 that a 2-connected graph G with no induced K1 , 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.

Original languageEnglish
Pages (from-to)663-690
Number of pages28
JournalGraphs and Combinatorics
Issue number3
Publication statusPublished - 2021 May


  • Claw-free graphs
  • Hamiltonian cycles
  • Induced nets

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Induced Nets and Hamiltonicity of Claw-Free Graphs'. Together they form a unique fingerprint.

Cite this