Semitotal domination in graphs: Partition and algorithmic results

In this paper, we study a parameter that is squeezed between arguably the two most important domination parameters, namely the domination number, 7(£), and the total domination number, 7 γ(G), of a graph G with no isolated vertex. A set S of vertices in G is a semitotal dominating set of G if S is a dominating set of G and every vertex in S is within distance 2 of another vertex of S. The semitotal domination number, γt2(G), is the minimum cardinality of a semitotal dominating set of G. We observe that 7(G) < γt2(G) < γ(G). Let G be a connected graph on at least three vertices. It is known that V{G) cannot always be partitioned into a dominating set and a total dominating set. However, in the case of semitotal domination we show that V(G) is partitionable into a dominating set and a semitotal dominating set. Furthermore, it is known that it is not always possible to partition V(G) into two total dominating sets, even for arbitrarily large minimum degree. We prove that if G is a connected graph on at least four vertices that is not a star, then V(G) can be partitioned into two semitotal dominating sets. We close with a discussion of algorithmic aspects of semitotal domination and present a polynomial-Time algorithm that utilizes a labeling method/scheme to compute the semitotal domination number of a tree.