J 2007

Tough spiders

KAISER, T; Daniel KRÁĽ a L STACHO

Základní údaje

Originální název

Tough spiders

Autoři

KAISER, T; Daniel KRÁĽ a L STACHO

Vydání

Journal of Graph Theory, HOBOKEN, Wiley, 2007, 0364-9024

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Utajení

není předmětem státního či obchodního tajemství

Impakt faktor

Impact factor: 0.503

Označené pro přenos do RIV

Ne

DOI

UT WoS

Klíčová slova anglicky

hamilton cycles; toughness; interval graphs; split graphs; matroids
Změněno: 6. 11. 2020 10:36, Mgr. Darina Boukalová

Anotace

V originále

Spider graphs are the intersection graphs of subtrees of subdivisions of stars. Thus, spider graphs are chordal graphs that form a common superclass of interval and split graphs. Motivated by previous results on the existence of Hamilton cycles in interval, split and chordal graphs, we show that every 3/2-tough spider graph is hamiltonian. The obtained bound is best possible since there are (3/2 - epsilon)-tough spider graphs that do not contain a Hamilton cycle. (C) 2007 Wiley Periodicals.