Dirac's minimum degree condition restricted to claws
Broersma, H.J. and Ryjacek, Z. and Schiermeyer, I. (1997) Dirac's minimum degree condition restricted to claws. Discrete Mathematics, 16716 . pp. 155166. ISSN 0012365X

PDF
638kB 
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 wellknown 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 1heavy (2heavy) 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 clawfree graph is 2heavy, and every 2heavy graph is 1heavy. We show that a 1heavy or a 2heavy 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. 
Item Type:  Article 
Copyright:  © 1997 Elsevier Science 
Faculty:  Electrical Engineering, Mathematics and Computer Science (EEMCS) 
Research Group:  
Link to this item:  http://purl.utwente.nl/publications/30146 
Official URL:  http://dx.doi.org/10.1016/S0012365X(96)002245 
Export this item as:  BibTeX EndNote HTML Citation Reference Manager 
Repository Staff Only: item control page
Metis ID: 140785