|
Citation:
|
KUŽEL, R., RYJÁČEK, Z., TESKA, J., VRÁNA, P. Closure, clique covering and degree conditions for Hamilton-connectedness in claw-free graphs. DISCRETE MATHEMATICS, 2012, roč. 312, č. 14, s. 2177-2189. ISSN: 0012-365X
|
|
Type:
|
ČLÁNEK
|
|
Language:
|
eng
|
|
English title:
|
Closure, clique covering and degree conditions for Hamilton-connectedness in claw-free graphs
|
|
Publication year:
|
2012
|
|
Authors:
|
Prof. RNDr. Zdeněk Ryjáček DrSc.
,
Prof. RNDr. Zdeněk Ryjáček DrSc.
,
RNDr. Mgr. Jakub Teska Ph.D.
,
Mgr. Petr Vrána
,
Ing. Roman Kužel Ph.D.
|
|
Abstract CZ:
|
V článku zesilujeme uzávěrovou operaci pro hamiltonovskou souvislost v grafech bez K(1,3), kterou zavedli druhý a čtvrtý autor, tak, že silný uzávěr grafu bez K(1,3) je hranový graf multigrafu s nejvýše dvěma trojúhelníky nebo nejvýše jednou dvojitou hranou. Pomocí silného uzávěru dokazujeme, že 3-souvislý graf G bez K(1,3) je hamiltonovsky souvislý, pokud G splňuje jednu z následujících podmínek: (i) G lze pokrýt nejvýše 5 klikami, (ii) G má minimální stupeň alespoň 4 a lze ho pokrýt nejvýše 6 klikami, (iii) G má minimální stupeň alespoň 6 a lze ho pokrýt nejvýše 7 klikami. Konečně, po revizi relace mezi stupňovými podmínkami a klikovými pokrytími pro případ silného uzávěru dokazujeme (jako důsledek výsledku o minimální sumě stupňů), že každý 3-souvislý graf bez K(1,3) s alespoň 142 uzly a minimálním stupněm alespoň (n+50)/8 je hamiltonovsky souvislý. Ukazujeme také, že naše výsledky jsou asymptoticky nejlepší možné.
|
|
Abstract EN:
|
We strengthen the closure concept for Hamilton-connectedness in claw-free graphs, introduced by the second and fourth authors, such that the strong closure of a claw-free graph is the line graph of a multigraph containing at most two triangles or at most one double edge. Using the concept of strong closure, we prove that a 3-connected claw-free graph G is Hamilton-connected if G satisfies one of the following: (i) G can be covered by at most 5 cliques, (ii) G has minimum degree at least 4 and can be covered by at most 6 cliques, (iii) G has minimum degree at least 6 and can be covered by at most 7 cliques. Finally, by reconsidering the relation between degree conditions and clique coverings in the case of the strong closure, we prove (as a corollary of a minimum degree sum result) that every 3-connected claw-free graph G of order at least 142 and minimum degree at least (n+50)/8 ) is Hamilton-connected. We also show that our results are asymptotically sharp.
|
|
Keywords
|
|