Pairs and triples of forbidden subgraphs and the existence of a 2-factor

被引：2

作者：

Aldred, R. E. L. ^{[1
]}

Fujisawa, Jun ^{[2
]}

Saito, Akira ^{[3
]}

机构：

[1] Univ Otago, Dept Math & Stat, Dunedin, New Zealand

[2] Keio Univ, Fac Business & Commerce, Kohoku Ku, Hiyoshi 4-1-1, Yokohama, Kanagawa 2238521, Japan

[3] Nihon Univ, Dept Informat Sci, Setagaya Ku, Sakurajosui 3-25-40, Tokyo 1568550, Japan

来源：

JOURNAL OF GRAPH THEORY | 2019年 / 90卷 / 01期

基金：

日本学术振兴会;

关键词：

2-factor; forbidden subgraph; HAMILTONIAN PROPERTIES; FREE GRAPHS; FINITE-SET;

D O I：

10.1002/jgt.22368

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Let H be a set of connected graphs, each of which has order at least three, and suppose that there exist infinitely many connected H-free graphs of minimum degree at least two and all except for finitely many of them have a 2-factor. In [J. Graph Theory, 64(2010), 250-266], we proved that if |H|<= 3, then one of the members in H is a star. In this article, we determine the remaining members of H and hence give a complete characterization of the pairs and triples of forbidden subgraphs.

引用

页码：61 / 82

页数：22

共 15 条

[1] Forbidden Subgraphs and the Existence of a 2-Factor [J].

Aldred, R. E. L. ;

Fujisawa, Jun ;

Saito, Akira .

JOURNAL OF GRAPH THEORY, 2010, 64 (03) :250-266

[2]

Chartrand G., 2011, Graphs and Digraphs

[3]

Chvatal V., 1972, Discrete Math, V2, P111, DOI DOI 10.1016/0012-365X(72)90079-9

[4]

Diestel R., 2006, Graph Theory

[5] Forbidden subgraphs that imply 2-factors [J].

Faudree, J. R. ;

Faudree, R. J. ;

Ryjacek, Z. .

DISCRETE MATHEMATICS, 2008, 308 (09) :1571-1582

[6]

Faudree R., 1995, Proceedings of the Twenty-sixth Southeastern International Conference on Combinatorics, Graph Theory and Computing, V109, P13

[7] Characterizing forbidden pairs for Hamiltonian properties [J].

Faudree, RJ ;

Gould, RJ .

DISCRETE MATHEMATICS, 1997, 173 (1-3) :45-60

[8] Forbidden subgraphs generating a finite set [J].

Fujisawa, Jun ;

Plummer, Michael D. ;

Saito, Akira .

DISCRETE MATHEMATICS, 2013, 313 (19) :1835-1842

[9] Forbidden induced subgraphs for star-free graphs [J].

Fujisawa, Jun ;

Ota, Katsuhiro ;

Ozeki, Kenta ;

Sueiro, Gabriel .

DISCRETE MATHEMATICS, 2011, 311 (21) :2475-2484

[10] A pair of forbidden subgraphs and perfect matchings [J].

Fujita, S ;

Kawarabayashi, K ;

Lucchesi, CL ;

Ota, K ;

Plummer, MD ;

Saito, A .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 2006, 96 (03) :315-324

← 1 2 →