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)\ge \lceil \frac{n+2}{3}\rceil$. In this note, we provide a simple constructive characterization of the extremal trees $T$ of order $n$ achieving this lower bound.