History

Please fill in your query. A complete syntax description you will find on the General Help page.
Forbidden subgraphs and the existence of a 2-factor. (English)
J. Graph Theory 64, No. 3, 250-266 (2010).
Summary: We consider forbidden subgraphs which force the existence of a 2-factor. Let ${\Cal G}$ be the class of connected graphs of minimum degree at least two and maximum degree at least three, and let ${\Cal F}_2$ be the class of graphs which have a 2-factor. For a set ${\Cal H}$ of connected graphs of order at least three, a graph $G$ is said to be ${\Cal H}$-free if no member of ${\Cal H}$ is an induced subgraph of $G$, and let ${\Cal G}({\Cal H})$ denote the class of graphs in ${\Cal G}$ that are ${\Cal H}$-free. We are interested in sets ${\Cal H}$ such that ${\Cal G}({\Cal H})$ is an infinite class while ${\Cal G}({\Cal H})-{\Cal F}_2$ is a finite class. In particular, we investigate whether ${\Cal H}$ must contain a star (i.e. $K_{1,n}$ for some positive integer $n$). We prove the following { indent=7mm \item{(1)}If $|{\Cal H}|= 1$, then ${\Cal H}= \{K_{1,2}\}$. \item{(2)}If $|{\Cal H}|= 2$, then ${\Cal H}$ contains $K_{1,2}$ or $K_{1,3}$. \item{(3)}If $|{\Cal H}|= 3$, then ${\Cal H}$ contains a star. But no restriction is imposed on the order of the star. \item{(4)}Not all of ${\Cal H}$ with $|{\Cal H}|= 4$ contain a star. } For $|{\Cal H}|\le 2$, we compare our results with a recent result by {\it J. R. Faudree}, {\it R. J. Faudree} and {\it Z. Ryjáček} [“Forbidden subgraphs that imply 2-factors,” Discrete Math. 308, No. 9, 1571‒1582 (2008; Zbl 1139.05049)], 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 ${\Cal H}$ does not contains a star but ${\Cal G}({\Cal H})-{\Cal G}(\{K_{1,t}\})$ is finite for some $t\ge 3$.