On traceability and 2-factors in claw-free graphs

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

ArticleOriginal scientific text

Title

On traceability and 2-factors in claw-free graphs

Authors ^1,², ^3,⁴, ⁵

Affiliations

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
Department of Mathematics, University of West Bohemia
Institute of Theoretical Computer Science, Charles University, Univerzitní 8, 306 14 Plzeň, Czech Republic
Faculty of Applied Mathematics, University of Mining and Metallurgy AGH, al. Mickiewicza 30, 30-059 Kraków, Poland

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.

Keywords

ENG

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

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

Title

On traceability and 2-factors in claw-free graphs

Affiliations

Abstract

Keywords

Bibliography