Semitotal domination in graphs
Wayne Goddard, Michael A. Henning, Charles A. McPillan · Utilitas Mathematica · 2014
In this paper 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 γt2(G), is the minimum cardinality of a semitotal dominating set of G. We show that if G is a connected graph on n ≥ 4 vertices, then γt2(G) ≤ n/2, and we characterize the trees and graphs of minimum degree 2 achieving this bound.