Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4649516 | Discrete Mathematics | 2010 | 10 Pages |
Abstract
We show that every K4K4-minor-free graph with toughness greater than 4/74/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/74/7-tough K4K4-minor-free graph with no 2-walk.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Zdeněk Dvořák, Daniel Král’, Jakub Teska,