Characterizations of trees with equal domination parameters

摘要

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 minimum cardinality of a restrained dominating set of G. A set S subset of or equal to V is a weak dominating set of G if, for every u in V - S, there exists a v is an element of S such that uv is an element of E and deg u greater than or equal to deg v. The weak domination number of G, denoted by gamma(w)(G), is the minimum cardinality of a weak dominating set of G. In this article, we provide a constructive characterization of those trees with equal independent domination and restrained domination numbers. A constructive characterization of those trees with equal independent domination and weak domination numbers is also obtained. (C) 2000 John Wiley & Sons, Inc. [References: 14]