Abstract
In this paper, we consider forbidden subgraphs which force the existence of a 2โfactor. Let \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}${\cal G}$\end{document} be the class of connected graphs of minimum degree at least two and maximum degree at least three, and let \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}${{\cal F}_2}$\end{document} be the class of graphs which have a 2โfactor. For a set \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}${\cal H}$\end{document} of connected graphs of order at least three, a graph G is said to be \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}${\cal H}$\end{document}โfree if no member of \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}${\cal H}$\end{document} is an induced subgraph of G, and let \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}${\cal G}({\cal H})$\end{document} denote the class of graphs in \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}${\cal G}$\end{document} that are \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}${\cal H}$\end{document}โfree. We are interested in sets \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}${\cal H}$\end{document} such that \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}${\cal G}({\cal H})$\end{document} is an infinite class while \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}${\cal G}({\cal H})-{\cal F}_2$\end{document} is a finite class. In particular, we investigate whether \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}${\cal H}$\end{document} must contain a star (i.e. K~1, n~ for some positive integer n). We prove the following:
If |\documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}${\cal H}$\end{document}|=1, then \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}${\cal H}$\end{document}={K~1, 2~}.
If |\documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}${\cal H}$\end{document}|=2, then \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}${\cal H}$\end{document} contains K~1, 2~ or K~1, 3~.
If |\documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}${\cal H}$\end{document}|=3, then \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}${\cal H}$\end{document} contains a star. But no restriction is imposed on the order of the star.
Not all of \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}${\cal H}$\end{document} with |\documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}${\cal H}$\end{document}|=4 contain a star.
For |\documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}${\cal H}$\end{document}|โฉฝ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 \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}${\cal H}$\end{document} does not contain a star but \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}${\cal G}$\end{document}(\documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}${\cal H}$\end{document})โ\documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}${\cal G}$\end{document}({K~1, t~}) is finite for some tโฉพ3. ยฉ 2009 Wiley Periodicals, Inc. J Graph Theory 64: 250โ266, 2010