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.
Abstract
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.
| Item Type: | Article |
|---|---|
| Keywords: | Claw-free graph, 2-factor, Minimum degree, Edge-degree. |
| Full text: | (AM) Accepted Manuscript Download PDF (442Kb) |
| Status: | Peer-reviewed |
| 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
| Export: | |
| Look up in GoogleScholar |
