Toughness threshold for the existence of 2-walks in K-4-minor-free graphs

DVORAK, Z; Daniel KRÁĽ a J TESKA. Toughness threshold for the existence of 2-walks in K-4-minor-free graphs. Discrete Mathematics. AMSTERDAM: Elsevier B. V., 2010, roč. 310, č. 3, s. 642-651. ISSN 0012-365X. Dostupné z: https://doi.org/10.1016/j.disc.2009.05.016.

Základní údaje

Originální název

Toughness threshold for the existence of 2-walks in K-4-minor-free graphs

Autoři

DVORAK, Z; Daniel KRÁĽ a J TESKA

Vydání

Discrete Mathematics, AMSTERDAM, Elsevier B. V. 2010, 0012-365X

---

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.536

DOI

https://doi.org/10.1016/j.disc.2009.05.016

UT WoS

000273114200035

Klíčová slova anglicky

Toughness; 2-walk; Series-parallel graph

---

Anotace

V originále

We show that every K-4-minor-free graph with toughness greater than 4/7 has a 2-walk, i.e., a closed walk visiting each vertex at most twice. We show that the bound cannot be improved by constructing a 4/7-tough K-4-minor-free graph with no 2-walk. (C) 2009 Elsevier B.V. All rights reserved.