2015/11/27 by José D. Alvarado, Alvarado, José D., Simone Dantas +3 · 1 citation
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO
paper · pdf · doi:10.48550/arxiv.1511.08713
arxiv created 2015/11/27 · arxiv updated 2015/11/30
For a maximal outerplanar graph G of order n at least 3, 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 5, 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 \cal 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 \cal Hk has a dominating set D of order at most \lfloor(kn)/(2k+1)\rfloor such that every component of the subgraph G[D] of G induced by D has order at least k.