Cookies

We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.


Durham Research Online
You are in:

Sharp upper bounds for the minimum number of components of 2-factors in claw-free graphs.

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:
Export
Look up in GoogleScholar