Bounds on the exponential domination number

As a natural variant of domination in graphs, Dankelmann et al. (2009) introduce exponential domination, where vertices are considered to have some dominating power that decreases exponentially with the distance, and the dominated vertices have to accumulate a sufficient amount of this power emanating from the dominating vertices. More precisely, if S is a set of vertices of a graph G, then S is an exponential dominating set of G if ∑v∈S12dist(G,S)(u,v)−1≥1 for every vertex u in V(G)∖S, where dist(G,S)(u,v) is the distance between u∈V(G)∖S and v∈S in the graph G−(S∖{v}). The exponential domination number γe(G) of G is the minimum order of an exponential dominating set of G.Dankelmann et al. show 14(d+2)≤γe(G)≤25(n+2)for a connected graph G of order n and diameter d. We provide further bounds and in particular strengthen their upper bound. Specifically, for a connected graph G of order n, maximum degree Δ at least 3, and radius r, we show γe(G)≥n13(Δ−1)2log2(Δ−1)+1log22(Δ−1)+log2(Δ−1)+1,γe(G)≤22r−2, and γe(G)≤43108(n+2).