Informace o publikaci
Toughness threshold for the existence of 2-walks in K-4-minor-free graphs
| Autoři | |
|---|---|
| Rok publikování | 2010 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | Discrete Mathematics |
| Citace | |
| Doi | http://dx.doi.org/10.1016/j.disc.2009.05.016 |
| Klíčová slova | Toughness; 2-walk; Series-parallel graph |
| Popis | 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. |