A Note on Restrained Domination in Trees.
Johannes H. Hattingh, Andrew R Plummer · 2010
Let G = (V, E) be a graph. A set S ⊆ V is a restrained dominating set if every vertex not in S is adjacent to a vertex in S and to a vertex in V − S. The restrained domination number of G, denoted by γr(G), is the smallest cardinality of a restrained dominating set of G. It is known that if T is a tree of order n, then γr(T) ≥ ⌈(n+2)/3⌉. In this note we provide a simple constructive characterization of the extremal trees T of order n achieving this lower bound. 1