Dominating sets inducing large components in maximal outerplanar graphs

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 2 n / 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 H k of graphs of order at least 4 k + 4 and at most 4 k 2 − 2 k such that every maximal outerplanar graph G of order n at least 2 k + 1 that does not belong to H k has a dominating set D of order at most ⌊ k n 2 k + 1 ⌋ such that every component of the subgraph G [ D ] of G induced by D has order at least k .