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|
|Date accepted:||No date available|
|Date deposited:||22 January 2015|
|Date of first online publication:||November 2009|
|Date first made open access:||No date available|
Save or Share this output
|Look up in GoogleScholar|