2-factors in claw-free graphs

• Autorzy: Guantao Chen , Jill R. Faudree , Ronald J. Gould , Akira Saito
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

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

Kategorie tematyczne

• 05C38: Paths and cycles

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2000
• Tom: 20
• Numer: 2
• Strony: 165-172

Daty

wydano

2000

otrzymano

1999-02-19

poprawiono

2000-01-24

Twórcy

autor

Guantao Chen

• Georgia State University, Atlanta, GA 30303

autor

Jill R. Faudree

• University of Alaska Fairbanks, Fairbanks, AK 99775

autor

Ronald J. Gould

• Emory University, Atlanta, GA 30322

autor

Akira Saito

• Nihon University, Tokyo 156, Japan

Bibliografia

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

Identyfikatory

DOI

10.7151/dmgt.1116