# zbMATH — the first resource for mathematics

Semitotal domination in graphs: partition and algorithmic results. (English) Zbl 1396.05085
Summary: We study a parameter that is squeezed between arguably the two most important domination parameters, namely the domination number, $$\gamma(G)$$, and the total domination number, $$\gamma_t(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, $$\gamma_{t2}(G)$$, is the minimum cardinality of a semitotal dominating set of $$G$$. We observe that $$\gamma(G)\leq\gamma_{t2}(G)\leq\gamma_t(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.

##### MSC:
 05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
##### Keywords:
domination; total domination; semitotal domination