DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

DOI 10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2017: 0.601

SCImago Journal Rank (SJR) 2017: 0.633

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

Discussiones Mathematicae Graph Theory

PDF

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

2-FACTORS IN CLAW-FREE GRAPHS

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

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

References

[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