Broersma, Hajo and Paulusma, Daniel and Yoshimoto, Kiyoshi (2009) 'Sharp upper bounds for the minimum number of components of 2-factors in claw-free graphs.', Graphs and combinatorics., 25 (4). pp. 427-460.
Let G be a claw-free graph with order n and minimum degree δ. We improve results of Faudree et al. and Gould & Jacobson, and solve two open problems by proving the following two results. If δ = 4, then G has a 2-factor with at most (5n − 14)/18 components, unless G belongs to a finite class of exceptional graphs. If δ ≥ 5, then G has a 2-factor with at most (n − 3)/(δ − 1) components, unless G is a complete graph. These bounds are best possible in the sense that we cannot replace 5/18 by a smaller quotient and we cannot replace δ − 1 by δ, respectively.
|Keywords:||Claw-free graph, 2-factor, Minimum degree, Edge-degree.|
|Full text:||(AM) Accepted Manuscript|
Download PDF (442Kb)
|Publisher Web site:||http://dx.doi.org/10.1007/s00373-009-0855-7|
|Publisher statement:||The final publication is available at Springer via http://dx.doi.org/10.1007/s00373-009-0855-7|
|Record Created:||15 Dec 2009 11:50|
|Last Modified:||22 Jan 2015 16:28|
|Social bookmarking:||Export: EndNote, Zotero | BibTex|
|Look up in GoogleScholar | Find in a UK Library|