Skip to main content
Article
Claw-Free Graphs and Separating Independent Sets On 2-Factors
Journal of Graph Theory
  • Ralph J. Faudree, University of Memphis
  • Colton Magnant, Georgia Southern University
  • Kenta Ozeki, National Institute for Informatics
  • Kiyoshi Yoshimoto, Nihon University
Document Type
Article
Publication Date
3-1-2012
DOI
10.1002/jgt.20579
Disciplines
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.

Citation Information
Ralph J. Faudree, Colton Magnant, Kenta Ozeki and Kiyoshi Yoshimoto. "Claw-Free Graphs and Separating Independent Sets On 2-Factors" Journal of Graph Theory Vol. 69 Iss. 3 (2012) p. 251 - 263
Available at: http://works.bepress.com/colton_magnant/31/