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:Full text not available from this repository.
Publisher Web site:http://dx.doi.org/10.1007/s00373-009-0855-7
Record Created:15 Dec 2009 11:50
Last Modified:03 Apr 2013 13:13

Social bookmarking: del.icio.usConnoteaBibSonomyCiteULikeFacebookTwitterExport: EndNote, Zotero | BibTex
Usage statisticsLook up in GoogleScholar | Find in a UK Library