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

Abstract

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

How to cite

top

Guantao 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. [1] J.A. Bondy, Pancyclic Graphs I, J. Combin. Theory (B) 11 (1971) 80-84, doi: 10.1016/0095-8956(71)90016-5. 
  2. [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. [3] G. Chartrand and L. Lesniak, Graphs & Digraphs (Chapman and Hall, London, 3rd edition, 1996). 
  4. [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. [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. [6] O. Ore, Hamiltonian Connected Graphs, J. Math. Pures. Appl. 42 (1963) 21-27. 
  7. [7] H. Li and C. Virlouvet, Neighborhood Conditions for Claw-free Hamiltonian Graphs, Ars Combinatoria 29 (A) (1990) 109-116. Zbl0709.05022

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.