Discussiones
Mathematicae Graph Theory 20(2) (2000) 165-172
DOI: https://doi.org/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
Close