Publication details
Toughness threshold for the existence of 2-walks in K-4-minor-free graphs
| Authors | |
|---|---|
| Year of publication | 2010 |
| Type | Article in Periodical |
| Magazine / Source | Discrete Mathematics |
| Citation | |
| Doi | http://dx.doi.org/10.1016/j.disc.2009.05.016 |
| Keywords | Toughness; 2-walk; Series-parallel graph |
| Description | 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. |