Premium
Forbidden subgraphs and the existence of a 2‐factor
Author(s) -
Aldred R. E. L.,
Fujisawa Jun,
Saito Akira
Publication year - 2010
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/jgt.20454
Subject(s) - combinatorics , graph , physics , mathematics
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: (1) 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 }. (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 . (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. (4) 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