Semipaired domination in maximal outerplanar graphs

摘要

A subset S of vertices in a graph G is a dominating set if every vertex in V(G)S is adjacent to a vertex in S. If the graph G has no isolated vertex, then a semipaired dominating set of G is a dominating set of G with the additional property that the set S can be partitioned into two element subsets such that the vertices in each subset are at most distance two apart. The semipaired domination number gamma(pr2)(G) is the minimum cardinality of a semipaired dominating set of G. Let G be amaximal outerplanar graph of order n with n(2) vertices of degree 2. We show that if n >= 5, then gamma(pr2)(G) = 2/5 n. Further, we show that if n >= 3, then gamma(pr2)(G) <= 1/3 (n + n(2)). Both bounds are shown to be tight.