DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

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

PDF

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

ON TRACEABILITY AND 2-FACTORS IN CLAW-FREE GRAPHS

Dalibor Froncek

Department of Mathematics and Statistics
University of Minnesota Duluth
Duluth, MN 55810, U.S.A.
and
Department of Applied Mathematics
Technical University of Ostrava
Ostrava, Czech Republic
e-mail: dfroncek@d.umn.edu

Zdenek Ryjácek

Department of Mathematics
University of West Bohemia
and
Institute of Theoretical Computer Science
Charles University
Univerzitní 8, 306 14 Plzen, Czech Republic
e-mail: ryjacek@kma.zcu.cz

Zdzisław Skupień

Faculty of Applied Mathematics
University of Mining and Metallurgy AGH
al. Mickiewicza 30, 30-059 Kraków, Poland
e-mail: skupien@uci.agh.edu.pl

Abstract

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.

References

[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