Article ID Journal Published Year Pages File Type
4650293 Discrete Mathematics 2007 12 Pages PDF
Abstract

In this paper, we prove that if a claw-free graph G   with minimum degree δ⩾4δ⩾4 has no maximal clique of two vertices, then G   has a 2-factor with at most (|G|-1)/4(|G|-1)/4 components. This upper bound is best possible. Additionally, we give a family of claw-free graphs with minimum degree δ⩾4δ⩾4 in which every 2-factor contains more than n/δn/δ components.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,