On the number of components in 2-factors of claw-free graphs |
| |
Authors: | Kiyoshi Yoshimoto |
| |
Institution: | Department of Mathematics, College of Science and Technology Nihon University, Tokyo 101-8308, Japan |
| |
Abstract: | In this paper, we prove that if a claw-free graph G with minimum degree δ?4 has no maximal clique of two vertices, then G has a 2-factor with at most (|G|-1)/4 components. This upper bound is best possible. Additionally, we give a family of claw-free graphs with minimum degree δ?4 in which every 2-factor contains more than n/δ components. |
| |
Keywords: | Claw-free graphs Line graphs 2-Factor |
本文献已被 ScienceDirect 等数据库收录! |
|