Restrained domination in trees

Let G = (V,E) be a graph. A set S subset of or equal to 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. We show that if T is a tree of order n, then gamma(r)(T) greater than or equal to [(n + 2)/3]. Moreover, we constructively characterize the extremal trees T of order n achieving this lower bound. (C) 2000 Elsevier Science B.V. All rights reserved.