ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory


Discussiones Mathematicae Graph Theory 24(1) (2004) 55-71
DOI: 10.7151/dmgt.1213


Dalibor Froncek

Department of Mathematics and Statistics
University of Minnesota Duluth
Duluth, MN 55810, U.S.A.
Department of Applied Mathematics
Technical University of Ostrava
Ostrava, Czech Republic

Zdenek Ryjácek

Department of Mathematics
University of West Bohemia
Institute of Theoretical Computer Science
Charles University
Univerzitní 8, 306 14 Plzen, Czech Republic

Zdzisław Skupień

Faculty of Applied Mathematics
University of Mining and Metallurgy AGH
al. Mickiewicza 30, 30-059 Kraków, Poland


If G is a claw-free graph of sufficiently large order n, satisfying a degree condition σ k > n+k2− 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 C 1,… ,C 8 such that every sufficiently large connected claw-free graph satisfying degree condition σ 6 (k) > n+19 (or, as a corollary, δ (G) > [(n+19)/6]) either belongs to ∪ i = 18 C i or is traceable.

Keywords: traceability, 2-factor, claw, degree condition, closure

2000 Mathematics Subject Classification: 05C45, 05C70.


[1] J.A. Bondy and U.S.R. Murty, Graph Theory with applications (Macmillan, London and Elsevier, New York, 1976).
[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.
[3] S. Brandt, O. Favaron and Z. Ryjácek, 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.
[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.
[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.
[6] O. Favaron, E. Flandrin, H. Li and Z. Ryjácek, 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.
[7] R.L. Graham, M. Grötschel and L. Lovász, eds., (Handbook of Combinatorics. North-Holland, 1995).
[8] R. Gould and M. Jacobson, Two-factors with few cycles in claw-free graphs, preprint 1999.
[9] O. Kovárík, M. Mulac and Z. Ryjácek, 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.
[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.
[12] Z. Ryjácek, On a closure concept in claw-free graphs, J. Combin. Theory (B) 70 (1997) 217-224, doi: 10.1006/jctb.1996.1732.
[13] Z. Ryjácek, 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.

Received 29 May 2001
Revised 14 November 2002