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

Share/Save/Bookmark

Broersma, Hajo and Paulusma, Daniël and Yoshimoto, Kiyoshi (2009) Sharp upper bounds on the minimum number of components of 2-factors in claw-free graphs. Graphs and Combinatorics, 25 (4). pp. 427-460. ISSN 0911-0119

[img] PDF
Restricted to UT campus only
: Request a copy
631kB
Abstract:Let $G$ be a claw-free graph with order $n$ and minimum degree $\delta$. We improve results of Faudree et al. and Gould & Jacobson, and solve two open problems by proving the following two results. If $\delta = 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 $\delts \ge 5$, then $G$ has a 2-factor with at most $(n - 3)/(\delta - 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 $\delta - 1$ by $\delta$, respectively.
Item Type:Article
Copyright:© 2009 Springer
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/70041
Official URL:http://dx.doi.org/10.1007/s00373-009-0855-7
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page