Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
418598 | Discrete Applied Mathematics | 2015 | 7 Pages |
Abstract
It is well known that a graph is outerplanar if and only if it is K4K4-minor free and K2,3K2,3-minor free. Campos and Wakabayashi (2013) recently proved that γ(G)≤⌊n+k4⌋ for any maximal outerplanar graph GG of order n≥3n≥3 with kk vertices of degree 2, where γ(G)γ(G) denotes the domination number of GG. Tokunaga (2013) provided a short proof for the above theorem. Based on some structural properties of K2,3K2,3-minor free graphs and K4K4-minor free graphs, applying the idea of Tokunaga we extend the theorem of Campos and Wakabayashi to all maximal K4K4-minor free graphs and all maximal K2,3K2,3-minor free graphs. We also disprove two conjectures of Tokunaga on planar graphs.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Tingting Zhu, Baoyindureng Wu,