Domination with exponential decay

AbstractLet G be a graph and S⊆V(G). For each vertex u∈S and for each v∈V(G)−S, we define d¯(u,v)=d¯(v,u) to be the length of a shortest path in 〈V(G)−(S−{u})〉 if such a path exists, and ∞ otherwise. Let v∈V(G). We define wS(v)=∑u∈S12d¯(u,v)−1 if v⁄∈S, and wS(v)=2 if v∈S. If, for each v∈V(G), we have wS(v)≥1, then S is an exponential dominating set. The smallest cardinality of an exponential dominating set is the exponential domination number, γe(G). In this paper, we prove: (i) that if G is a connected graph of diameter d, then γe(G)≥(d+2)/4, and, (ii) that if G is a connected graph of order n, then γe(G)≤25(n+2)