Domination with exponential decay

Let G be a graph and S subset of V(G). For each vertex u is an element of S and foreach nu is an element of V(G) - S, we define (d) over bar (u, nu) = (d) over bar(nu, u) to be the length of a shortest path in < V(G)-(S- {u})> if such a path exists, and infinity otherwise. Let nu is an element of V(G). We define w(S)(nu) Sigma(u is an element of S) 1/2d(u,nu)-1 if nu is not an element of S, and w(S)(nu) = 2 if nu is an element of S. If, for each nu is an element of V(G), we have w(S)(nu) >= 1, then S is an exponential dominating set. The smallest cardinality of an exponential dominating set is the exponential domination number, gamma(e)(G). In this paper, we prove: (i) that if G is a connected graph of diameter d, then gamma(e)(G) >= (d + 2)/4, and, (ii) that if G is a connected graph of order n, then gamma(e)(G) <= 2/5 (n + 2). (C) 2008 Elsevier B.V. All rights reserved.