Hostname: page-component-5cf477f64f-bmd9x Total loading time: 0 Render date: 2025-04-05T16:15:12.563Z Has data issue: false hasContentIssue false
  • English
  • Français

Minimum Degree and Disjoint Cycles in Claw-Free Graphs

Published online by Cambridge University Press:  02 February 2012

RALPH J. FAUDREE ,
RONALD J. GOULD  and
MICHAEL S. JACOBSON
RALPH J. FAUDREE
Affiliation:
University of Memphis, Memphis, TN 38152, USA (e-mail: [email protected])
RONALD J. GOULD
Affiliation:
Emory University, Atlanta, GA 30322, USA (e-mail: [email protected])
MICHAEL S. JACOBSON
Affiliation:
University of Colorado Denver, Denver, CO 80217, USA (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

A graph is claw-free if it does not contain an induced subgraph isomorphic to K1,3. Cycles in claw-free graphs have been well studied. In this paper we extend results on disjoint cycles in claw-free graphs satisfying certain minimum degree conditions. In particular, we prove that if G is claw-free of sufficiently large order n = 3k with δ(G) ≥ n/2, then G contains k disjoint triangles.

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 21 , Issue 1-2: Honouring the Memory of Richard H. Schelp , March 2012 , pp. 129 - 139
Copyright
Copyright © Cambridge University Press 2012

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Chen, G., Faudree, J. R., Gould, R. J. and Saito, A. (2000) 2-factors in claw-free graphs. Discuss. Math. Graph Theory 20 165–172.CrossRefGoogle Scholar
[2]Chen, G., Markus, L. and Schelp, R. (1995) Vertex disjoint cycles for star-free graphs. Australas. J. Combin. 11 157–167.Google Scholar
[3]Corradi, K. and Hajnal, A. (1963) On the maximal number of independent circuits in a graph. Acta Math. Acad. Sci. Hungar. 14 423–439.CrossRefGoogle Scholar
[4]Li, Y., Rousseau, C. and Zang, W. (2000) Asymptotic upper bounds for Ramsey functions. Graphs Combin. 17 123–128.CrossRefGoogle Scholar
[5]Wang, H. (1998) Vertex-disjoint triangles in claw-free graphs with minimum degree at least three. Combinatorica 18 441–447.CrossRefGoogle Scholar