Sharp Upper Bounds on the Minimum Number of Components of 2-factors in Claw-free Graphs |
| |
Authors: | Hajo Broersma Daniël Paulusma Kiyoshi Yoshimoto |
| |
Institution: | 1.Department of Computer Science,Durham University, Science Laboratories,Durham,England;2.Department of Mathematics,College of Science and Technology, Nihon University,Tokyo,Japan |
| |
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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|