Bounds on the weak domination number.
Dieter Rautenbach · 1998
Let G = (V, E) a graph. A set D ~ V is a weak dominating set of G if for every vertex y E V- D there is a vertex xED with xy E E and d ( x, G)::; d(y, G). The weak domination number rw (G) is defined as the minimum cardinality of a weak dominating set and was introduced by Sampathkumar and Pushpa Latha in [6]. In this paper we present sharp upper bounds on rw(G) for general graphs involving the maximum and minimum degree and characterize all extremal graphs. Furthermore, we give a probabilistic upper bound and a lower bound on rw ( G). 1.