On traceability and 2-factors in claw-free graphs

Dalibor Fronček; Zdeněk Ryjáček; Zdzisław Skupień

Discussiones Mathematicae Graph Theory (2004)

  • Volume: 24, Issue: 1, page 55-71
  • ISSN: 2083-5892

Abstract

top
If G is a claw-free graph of sufficiently large order n, satisfying a degree condition σₖ > n + k² - 4k + 7 (where k is an arbitrary constant), then G has a 2-factor with at most k - 1 components. As a second main result, we present classes of graphs ₁,...,₈ such that every sufficiently large connected claw-free graph satisfying degree condition σ₆(k) > n + 19 (or, as a corollary, δ(G) > (n+19)/6) either belongs to ⋃ ⁸ i = 1 i or is traceable.

How to cite

top

Dalibor Fronček, Zdeněk Ryjáček, and Zdzisław Skupień. "On traceability and 2-factors in claw-free graphs." Discussiones Mathematicae Graph Theory 24.1 (2004): 55-71. <http://eudml.org/doc/270393>.

@article{DaliborFronček2004,
abstract = {If G is a claw-free graph of sufficiently large order n, satisfying a degree condition σₖ > n + k² - 4k + 7 (where k is an arbitrary constant), then G has a 2-factor with at most k - 1 components. As a second main result, we present classes of graphs ₁,...,₈ such that every sufficiently large connected claw-free graph satisfying degree condition σ₆(k) > n + 19 (or, as a corollary, δ(G) > (n+19)/6) either belongs to $⋃ ⁸_\{i=1\} _i$ or is traceable.},
author = {Dalibor Fronček, Zdeněk Ryjáček, Zdzisław Skupień},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {traceability; 2-factor; claw; degree condition; closure; independence number; clique covering number; Hamiltonian; claw-free graph},
language = {eng},
number = {1},
pages = {55-71},
title = {On traceability and 2-factors in claw-free graphs},
url = {http://eudml.org/doc/270393},
volume = {24},
year = {2004},
}

TY - JOUR
AU - Dalibor Fronček
AU - Zdeněk Ryjáček
AU - Zdzisław Skupień
TI - On traceability and 2-factors in claw-free graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2004
VL - 24
IS - 1
SP - 55
EP - 71
AB - If G is a claw-free graph of sufficiently large order n, satisfying a degree condition σₖ > n + k² - 4k + 7 (where k is an arbitrary constant), then G has a 2-factor with at most k - 1 components. As a second main result, we present classes of graphs ₁,...,₈ such that every sufficiently large connected claw-free graph satisfying degree condition σ₆(k) > n + 19 (or, as a corollary, δ(G) > (n+19)/6) either belongs to $⋃ ⁸_{i=1} _i$ or is traceable.
LA - eng
KW - traceability; 2-factor; claw; degree condition; closure; independence number; clique covering number; Hamiltonian; claw-free graph
UR - http://eudml.org/doc/270393
ER -

References

top
  1. [1] J.A. Bondy and U.S.R. Murty, Graph Theory with applications (Macmillan, London and Elsevier, New York, 1976). Zbl1226.05083
  2. [2] V. Chvátal and P. Erdős, A note on hamiltonian circuits, Discrete Math. 2 (1972) 111-113, doi: 10.1016/0012-365X(72)90079-9. Zbl0233.05123
  3. [3] S. Brandt, O. Favaron and Z. Ryjáček, Closure and stable hamiltonian properties in claw-free graphs, J. Graph Theory 32 (2000) 30-41, doi: 10.1002/(SICI)1097-0118(200005)34:1<30::AID-JGT4>3.0.CO;2-R Zbl0946.05053
  4. [4] G.A. Dirac, In abstrakten Graphen vorhandene vollständige 4-Graphen und ihre Unterteilungen, Math. Nachr. 22 (1960) 61-85, doi: 10.1002/mana.19600220107. Zbl0096.17903
  5. [5] R. Faudree, O. Favaron, E. Flandrin, H. Li and Z.Liu, On 2-factors in claw-free graphs, Discrete Math. 206 (1999) 131-137, doi: 10.1016/S0012-365X(98)00398-7. Zbl0981.05084
  6. [6] O. Favaron, E. Flandrin, H. Li and Z. Ryjáček, Clique covering and degree conditions for hamiltonicity in claw-free graphs, Discrete Math. 236 (2001) 65-80, doi: 10.1016/S0012-365X(00)00432-5. Zbl0995.05090
  7. [7] R.L. Graham, M. Grötschel and L. Lovász, eds., (Handbook of Combinatorics. North-Holland, 1995). Zbl0833.05001
  8. [8] R. Gould and M. Jacobson, Two-factors with few cycles in claw-free graphs, preprint 1999. Zbl0979.05084
  9. [9] O. Kovárík, M. Mulac and Z. Ryjáček, A note on degree conditions for hamiltonicity in 2-connected claw-free graphs, Discrete Math. 244 (2002) 253-268, doi: 10.1016/S0012-365X(01)00088-7. Zbl0992.05051
  10. [10] H. Li, A note on hamiltonian claw-free graphs, Rapport de Recherche LRI No. 1022 (Univ. de Paris-Sud, 1996), submitted. 
  11. [11] F. Harary and C. St.J.A. Nash-Williams, On eulerian and hamiltonian graphs and line graphs, Canad. Math. Bull. 8 (1965) 701-709, doi: 10.4153/CMB-1965-051-3. Zbl0136.44704
  12. [12] Z. Ryjáček, On a closure concept in claw-free graphs, J. Combin. Theory (B) 70 (1997) 217-224, doi: 10.1006/jctb.1996.1732. Zbl0872.05032
  13. [13] Z. Ryjáček, A. Saito and R.H. Schelp, Closure, 2-factors and cycle coverings in claw-free graphs, J. Graph Theory 32 (1999) 109-117, doi: 10.1002/(SICI)1097-0118(199910)32:2<109::AID-JGT1>3.0.CO;2-O Zbl0932.05045

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.