zbMATH — the first resource for mathematics

Semitotal domination in graphs. (English) Zbl 1300.05220
Summary: We introduce a parameter that is squeezed between arguably the two most important domination parameters, namely the domination number and the total domination number. We define a set $$S$$ of vertices in a graph $$G$$ with no isolated vertices to be a semitotal dominating set of $$G$$ if it is a dominating set of $$G$$ and every vertex in $$S$$ is within distance 2 of another vertex of $$S$$. The semitotal domination number, denoted by $$\gamma_{t2}(G)$$, is the minimum cardinality of a semitotal dominating set of $$G$$.
We show that if $$G$$ is a connected graph on $$n\geq 4$$ vertices, then $$\gamma_{t2}(G)\leq n/2$$, and we characterize the trees and graphs of minimum degree 2 achieving this bound.

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