Abstract
In this paper, we consider forbidden subgraphs which force the existence of a 2-factor. Let g be the class of connected graphs of minimum degree at least two and maximum degree at least three, and let F-2 be the class of graphs which have a 2-factor. For a set H of connected graphs of order at least three, a graph G is said to be H-free if no member of H is an induced subgraph of G, and let g(H) denote the class of graphs in g that are H-free. We are interested in sets H such that g(H) is an infinite class while g(H)-F-2 is a finite class. In particular, we investigate whether H must contain a star (i.e. K-1,K-n, for some positive integer n). We prove the following.
(1) If |H| = 1, then 7-1 = {K1,2}.
(2) If |H| = 2, then H contains K-1,K-2 or K-1,K-3.
(3) If |H| = 3, then H contains a star. But no restriction is imposed on the order of the star.
(4) Not all of H with |H| = 4 contain a star.
For |H| <= 2, we compare our results with a recent result by Faudree et al. (Discrete Math 308 (2008), 1571-1582), and report a difference in the conclusion when connected graphs are considered as opposed to 2-connected graphs. We also observe a phenomenon in which does not contain a star but G(H)-G({K-1,K-t)} is finite for some t >= 3. (C) 2009 Wiley Periodicals, Inc. J Graph Theory 64: 250-266, 2010