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$ for every vertex $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\})$. The exponential domination number $\gamma_e(G)$ of $G$ is the minimum order of an exponential dominating set of $G$. Dankelmann et al. show $$\frac{ 1}{ 4}({ \rm d}+2)\leq \gamma_e(G)\leq \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 $\Delta$ at least $3$, radius ${ \rm 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*}
Categories: math.CO