ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2019: 0.755

SCImago Journal Rank (SJR) 2019: 0.600

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory


Discussiones Mathematicae Graph Theory 20(2) (2000) 165-172
DOI: 10.7151/dmgt.1116


Guantao Chen

Georgia State University, Atlanta, GA 30303

Jill R. Faudree

University of Alaska Fairbanks, Fairbanks, AK 99775

Ronald J. Gould

Emory University, Atlanta, GA 30322

Akira Saito

Nihon University, Tokyo 156, Japan


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.

Keywords: claw-free, forbidden subgraphs, 2-factors, cycles.

2000 Mathematics Subject Classification: 05C38.


[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.
[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.
[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.

Received 19 February 1999
Revised 24 January 2000