Bounds on the Exponential Domination Number

As a natural variant of domination in graphs, Dankelmann et al. [Domination with exponential decay, Discrete Math. 309 (2009) 5877-5883] 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 $\sum\limits_{v\in S}\left(\frac{1}{2}\right)^{{\rm dist}{(G,S)}(u,v)-1}\geq 1$foreveryvertex$u$in$V(G)\setminus S$,where${\rm dist}{(G,S)}(u,v)$ is the distance between $u\in V(G)\setminus S$ and $v\in S$ in the graph $G-(S\setminus { v})$\mathrm{.}Theexponentialdominationnumber$\gamma_e(G)$of$G$ is the minimum order of an exponential dominating set of $G$. Dankelmann et al. show $$\frac{1}{4}(\mathrm{d}+2)\le {\gamma }_e(G)\le \frac{2}{5}(n+2)$$ for a connected graph $G$ of order $n$ and diameter ${\rm d}$. We provide further bounds and in particular strengthen their upper bound. Specifically, for a connected graph $G$ of order $n$, maximum degree $\mathrm{\Delta }$ at least $3$, radius $\mathrm{r}$ at least $1$, we show \begin{eqnarray*} \gamma_e(G) & \geq & \left(\frac{n}{13(\Delta-1)^2}\right)^{\frac{\log_2(\Delta-1)+1}{\log_2^2(\Delta-1)+\log_2(\Delta-1)+1}},\[3mm] \gamma_e(G) & \leq & 2^{2{\rm r}-2}\mbox{, and }\[3mm] \gamma_e(G) & \leq & \frac{43}{108}(n+2). \end{eqnarray*}