Hamilton cycles in claw-heavy graphs

Bing Chen, Shenggui Zhang, Shengning Qiao

Research output: Contribution to journalArticlepeer-review

11 Scopus citations

Abstract

A graph G on n ≥ 3 vertices is called claw-heavy if every induced claw (K1, 3) of G has a pair of nonadjacent vertices such that their degree sum is at least n. In this paper we show that a claw-heavy graph G has a Hamilton cycle if we impose certain additional conditions on G involving numbers of common neighbors of some specific pair of nonadjacent vertices, or forbidden induced subgraphs. Our results extend two previous theorems of Broersma, Ryjáček and Schiermeyer [H.J. Broersma, Z. Ryjáček, I. Schiermeyer, Dirac's minimum degree condition restricted to claws, Discrete Math. 167-168 (1997) 155-166], on the existence of Hamilton cycles in 2-heavy graphs.

Original languageEnglish
Pages (from-to)2015-2019
Number of pages5
JournalDiscrete Mathematics
Volume309
Issue number8
DOIs
StatePublished - 28 Apr 2009

Keywords

  • 2-heavy graph
  • Claw-heavy graph
  • Hamilton cycle

Fingerprint

Dive into the research topics of 'Hamilton cycles in claw-heavy graphs'. Together they form a unique fingerprint.

Cite this