×

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.)
PDF BibTeX XML Cite