2-factors in claw-free graphs
Guantao Chen ; Jill R. Faudree ; Ronald J. Gould ; Akira Saito
Discussiones Mathematicae Graph Theory, Tome 20 (2000), p. 165-172 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

We consider the question of the range of the number of cycles possible in a 2-factor of a 2-connected claw-free graph with sufficiently high minimum degree. (By claw-free we mean the graph has no induced K1,3.) In particular, we show that for such a graph G of order n ≥ 51 with δ(G) ≥ (n-2)/3, G contains a 2-factor with exactly k cycles, for 1 ≤ k ≤ (n-24)/3. We also show that this result is sharp in the sense that if we lower δ(G), we cannot obtain the full range of values for k.

Publié le : 2000-01-01
EUDML-ID : urn:eudml:doc:270284 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1116,
     author = {Guantao Chen and Jill R. Faudree and Ronald J. Gould and Akira Saito},
     title = {2-factors in claw-free graphs},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {20},
     year = {2000},
     pages = {165-172},
     zbl = {0979.05067},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1116}
}

Guantao Chen; Jill R. Faudree; Ronald J. Gould; Akira Saito. 2-factors in claw-free graphs. Discussiones Mathematicae Graph Theory, Tome 20 (2000) pp. 165-172. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1116/

[000] [1] J.A. Bondy, Pancyclic Graphs I, J. Combin. Theory (B) 11 (1971) 80-84, doi: 10.1016/0095-8956(71)90016-5.

[001] [2] S. Brandt, G. Chen, R.J. Faudree, R.J. Gould and L. Lesniak, On the Number of Cycles in a 2-Factor, J. Graph Theory, 24 (1997) 165-173, doi: 10.1002/(SICI)1097-0118(199702)24:2<165::AID-JGT4>3.3.CO;2-A

[002] [3] G. Chartrand and L. Lesniak, Graphs & Digraphs (Chapman and Hall, London, 3rd edition, 1996).

[003] [4] R.J. Gould, Updating the Hamiltonian Problem - A Survey, J. Graph Theory 15 (1991) 121-157, doi: 10.1002/jgt.3190150204. | Zbl 0746.05039

[004] [5] M.M. Matthews and D.P. Sumner, Longest Paths and Cycles in K1,3-Free Graphs, J. Graph Theory 9 (1985) 269-277, doi: 10.1002/jgt.3190090208. | Zbl 0591.05041

[005] [6] O. Ore, Hamiltonian Connected Graphs, J. Math. Pures. Appl. 42 (1963) 21-27.

[006] [7] H. Li and C. Virlouvet, Neighborhood Conditions for Claw-free Hamiltonian Graphs, Ars Combinatoria 29 (A) (1990) 109-116. | Zbl 0709.05022