Abstract | ||
---|---|---|
For a maximal outerplanar graph G of order n at least three, Matheson and Tarjan showed that G has domination number at most n/3. Similarly, for a maximal outerplanar graph G of order n at least five, Dorfling, Hattingh, and Jonck showed, by a completely different approach, that G has total domination number at most 2n/5 unless G is isomorphic to one of two exceptional graphs of order 12. We present a unified proof of a common generalization of these two results. For every positive integer k, we specify a set Hk of graphs of order at least 4k+4 and at most 4k2-2k such that every maximal outerplanar graph G of order n at least 2k+1 that does not belong to Hk has a dominating set D of order at most kn2k+1 such that every component of the subgraph G[D] of G induced by D has order at least k. |
Year | DOI | Venue |
---|---|---|
2018 | 10.1002/jgt.22217 | JOURNAL OF GRAPH THEORY |
Keywords | Field | DocType |
domination,maximal outerplanar graph,total domination | Integer,Graph,Discrete mathematics,Outerplanar graph,Combinatorics,Dominating set,Isomorphism,Domination analysis,Mathematics | Journal |
Volume | Issue | ISSN |
88.0 | 2.0 | 0364-9024 |
Citations | PageRank | References |
0 | 0.34 | 7 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
José D. Alvarado | 1 | 7 | 3.82 |
Simone Dantas | 2 | 119 | 24.99 |
Dieter Rautenbach | 3 | 946 | 138.87 |