A Note on Restrained Domination in Trees

Abstract

Let \(G = (V, E)\) be a graph. A set \(S \subseteq 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 \(\gamma_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 \(\gamma_r(T) \geq \left\lceil \frac{n+2}{3} \right\rceil\). In this note, we provide a simple constructive characterization of the extremal trees \(T\) of order \(n\) achieving this lower bound.