Dirac's minimum degree condition restricted to claws

Haitze J. Broersma, Z. Ryjacek, I. Schiermeyer

Research output: Contribution to journalArticleAcademicpeer-review

23 Citations (Scopus)
94 Downloads (Pure)

Abstract

Let G be a graph on n 3 vertices. Dirac's minimum degree condition is the condition that all vertices of G have degree at least . This is a well-known sufficient condition for the existence of a Hamilton cycle in G. We give related sufficiency conditions for the existence of a Hamilton cycle or a perfect matching involving a restriction of Dirac's minimum degree condition to certain subsets of the vertices. For this purpose we define G to be 1-heavy (2-heavy) if at least one (two) of the end vertices of each induced subgraph of G isomorphic to K1,3 (a claw) has (have) degree at least . Thus, every claw-free graph is 2-heavy, and every 2-heavy graph is 1-heavy. We show that a 1-heavy or a 2-heavy graph G has a Hamilton cycle or a perfect matching if we impose certain additional conditions on G involving numbers of common neighbours, (local) connectivity, and forbidden induced subgraphs. These results generalize or extend previous work of Broersma & Veldman, Dirac, Fan, Faudree et al., Goodman & Hedetniemi, Las Vergnas, Oberly & Sumner, Ore, Shi, and Sumner.
Original languageEnglish
Pages (from-to)155-166
Number of pages12
JournalDiscrete mathematics
Volume167-168
DOIs
Publication statusPublished - 15 Apr 1997

Keywords

  • Hamilton cycle
  • Hamiltonian graph
  • minimum degree condition
  • induced subgraph
  • claw
  • claw-free graph
  • local connectivity
  • 1-tough graph
  • perfect matching

Fingerprint

Dive into the research topics of 'Dirac's minimum degree condition restricted to claws'. Together they form a unique fingerprint.

Cite this