Claw‐free graphs and 2‐factors that separate independent vertices |
| |
| Authors: | Ralph J. Faudree Colton Magnant Kenta Ozeki Kiyoshi Yoshimoto |
| |
| Affiliation: | 1. Department of Mathematical Sciences, University of Memphis, , Memphis, Tennessee, 38152;2. Department of Mathematics, Lehigh University, , Bethlehem, Pennsylvania, 18015;3. National Institute of Informatics, , Tokyo, 101‐8430 JapanKenta Ozeki is a Research Fellow of the Japan Society for the Promotion of Science.;4. Department of Mathematics, Nihon University, , Tokyo, 101‐8308 Japan |
| |
| Abstract: | In this article, we prove that a line graph with minimum degree δ≥7 has a spanning subgraph in which every component is a clique of order at least three. This implies that if G is a line graph with δ≥7, then for any independent set S there is a 2‐factor of G such that each cycle contains at most one vertex of S. This supports the conjecture that δ≥5 is sufficient to imply the existence of such a 2‐factor in the larger class of claw‐free graphs. It is also shown that if G is a claw‐free graph of order n and independence number α with δ≥2n/α?2 and n≥3α3/2, then for any maximum independent set S, G has a 2‐factor with α cycles such that each cycle contains one vertex of S. This is in support of a conjecture that δ≥n/α≥5 is sufficient to imply the existence of a 2‐factor with α cycles, each containing one vertex of a maximum independent set. © 2011 Wiley Periodicals, Inc. J Graph Theory 69: 251–263, 2012 |
| |
| Keywords: | |
|
|
