抄録
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 Gis 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. K1,n for some positive integer n). We prove the following. (1) If |H|=1, then H={K1,2}. (2) If |H|=2, then H contains K1,2 or K1,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 H does not contain a star but G(H)-G({K1,t}) is finite for some t≥3.
| 本文言語 | English |
|---|---|
| ページ(範囲) | 250-266 |
| ページ数 | 17 |
| ジャーナル | Journal of Graph Theory |
| 巻 | 64 |
| 号 | 3 |
| DOI | |
| 出版ステータス | Published - 2010 7月 |
| 外部発表 | はい |
ASJC Scopus subject areas
- 幾何学とトポロジー
- 離散数学と組合せ数学
フィンガープリント
「Forbidden subgraphs and the existence of a 2-factor」の研究トピックを掘り下げます。これらがまとまってユニークなフィンガープリントを構成します。引用スタイル
- APA
- Standard
- Harvard
- Vancouver
- Author
- BIBTEX
- RIS