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 . 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 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 of graphs of order at least and at most such that every maximal outerplanar graph G of order n at least that does not belong to has a dominating set D of order at most such that every component of the subgraph of G induced by D has order at least k .