Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
5776801 | Discrete Mathematics | 2017 | 8 Pages |
Abstract
We discuss the existence of minors of given graphs in optimal 1-planar graphs. As our first main result, we prove that for any graph H, there exists an optimal 1-planar graph which contains H as a topological minor. Next, we consider minors of complete graphs. It is easily obtained from Mader's result (Mader, 1968) that every optimal 1-planar graph has a K6-minor. In the paper, we characterize optimal 1-planar graphs having no K7-minor.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Yusuke Suzuki,