Back to University of Twente portal
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, 167-16 . pp. 155-166. ISSN 0012-365X
![[img]](http://doc.utwente.nl/style/images/fileicons/application_pdf.png)
| PDF 623Kb |
| 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. |
| 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/S0012-365X(96)00224-5 |
| Export this item as: | BibTeX EndNote HTML Citation Reference Manager |
Show download statistics for this publication
Show download statistics for this publicationRepository Staff Only: item control page
Metis ID: 140785