# 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

## Access Full Article

top## Abstract

top## How to cite

topDalibor 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] J.A. Bondy and U.S.R. Murty, Graph Theory with applications (Macmillan, London and Elsevier, New York, 1976). Zbl1226.05083
- [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] 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] 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] 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] 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] R.L. Graham, M. Grötschel and L. Lovász, eds., (Handbook of Combinatorics. North-Holland, 1995). Zbl0833.05001
- [8] R. Gould and M. Jacobson, Two-factors with few cycles in claw-free graphs, preprint 1999. Zbl0979.05084
- [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] H. Li, A note on hamiltonian claw-free graphs, Rapport de Recherche LRI No. 1022 (Univ. de Paris-Sud, 1996), submitted.
- [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] 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] 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