Premium
Degree conditions for 2‐factors
Author(s) -
Brandt Stephan,
Chen Guantao,
Faudree Ralph,
Gould Ronald J.,
Lesniak Linda
Publication year - 1997
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/(sici)1097-0118(199702)24:2<165::aid-jgt4>3.0.co;2-o
Subject(s) - combinatorics , mathematics , graph , disjoint sets , degree (music) , regular graph , discrete mathematics , vertex (graph theory) , hamiltonian path , graph power , line graph , physics , acoustics
For any positive integer k , we investigate degree conditions implying that a graph G of order n contains a 2‐factor with exactly k components (vertex disjoint cycles). In particular, we prove that for k ≤ ( n /4), Ore's classical condition for a graph to be hamiltonian ( k = 1) implies that the graph contains a 2‐factor with exactly k components. We also obtain a sufficient degree condition for a graph to have k vertex disjoint cycles, at least s of which are 3‐cycles and the remaining are 4‐cycles for any s ≤ k . © 1997 John Wiley & Sons, Inc.