Article ID Journal Published Year Pages File Type
4653868 European Journal of Combinatorics 2013 9 Pages PDF
Abstract

For s≥3s≥3 a graph is K1,sK1,s-free if it does not contain an induced subgraph isomorphic to K1,sK1,s. Cycles in K1,3K1,3-free graphs, called 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 to K1,sK1,s-free graphs, normally called generalized claw-free graphs. In particular, we prove that if GG is K1,sK1,s-free of sufficiently large order n=3kn=3k with δ(G)≥n/2+cδ(G)≥n/2+c for some constant c=c(s)c=c(s), then GG contains kk disjoint triangles. Analogous results with the complete graph K3K3 replaced by a complete graph KmKm for m≥3m≥3 will be proved. Also, the existence of 22-factors for K1,sK1,s-free graphs with minimum degree conditions will be shown.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , ,