# 2-factors in claw-free graphs

Guantao Chen; Jill R. Faudree; Ronald J. Gould; Akira Saito

Discussiones Mathematicae Graph Theory (2000)

- Volume: 20, Issue: 2, page 165-172
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topGuantao Chen, et al. "2-factors in claw-free graphs." Discussiones Mathematicae Graph Theory 20.2 (2000): 165-172. <http://eudml.org/doc/270284>.

@article{GuantaoChen2000,

abstract = {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 $K_\{1,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.},

author = {Guantao Chen, Jill R. Faudree, Ronald J. Gould, Akira Saito},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {claw-free; forbidden subgraphs; 2-factors; cycles},

language = {eng},

number = {2},

pages = {165-172},

title = {2-factors in claw-free graphs},

url = {http://eudml.org/doc/270284},

volume = {20},

year = {2000},

}

TY - JOUR

AU - Guantao Chen

AU - Jill R. Faudree

AU - Ronald J. Gould

AU - Akira Saito

TI - 2-factors in claw-free graphs

JO - Discussiones Mathematicae Graph Theory

PY - 2000

VL - 20

IS - 2

SP - 165

EP - 172

AB - 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 $K_{1,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.

LA - eng

KW - claw-free; forbidden subgraphs; 2-factors; cycles

UR - http://eudml.org/doc/270284

ER -

## References

top- [1] J.A. Bondy, Pancyclic Graphs I, J. Combin. Theory (B) 11 (1971) 80-84, doi: 10.1016/0095-8956(71)90016-5.
- [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
- [3] G. Chartrand and L. Lesniak, Graphs & Digraphs (Chapman and Hall, London, 3rd edition, 1996).
- [4] R.J. Gould, Updating the Hamiltonian Problem - A Survey, J. Graph Theory 15 (1991) 121-157, doi: 10.1002/jgt.3190150204. Zbl0746.05039
- [5] M.M. Matthews and D.P. Sumner, Longest Paths and Cycles in ${K}_{1,3}$-Free Graphs, J. Graph Theory 9 (1985) 269-277, doi: 10.1002/jgt.3190090208. Zbl0591.05041
- [6] O. Ore, Hamiltonian Connected Graphs, J. Math. Pures. Appl. 42 (1963) 21-27.
- [7] H. Li and C. Virlouvet, Neighborhood Conditions for Claw-free Hamiltonian Graphs, Ars Combinatoria 29 (A) (1990) 109-116. Zbl0709.05022