Bounds on the Exponential Domination Number

Abstract

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 _{v\in S}{\left(\frac{1}{2}\right)}^{{\mathrm{dist}}_{(G,S)}(u,v)-1}\ge 1$ for every vertex $u$ in $V(G)\setminus S$, where ${\mathrm{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}(\mathrm{d}+2)\le {\gamma }_e(G)\le \frac{2}{5}(n+2)$$ for a connected graph $G$ of order $n$ and diameter $\mathrm{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 $\mathrm{r}$ at least $1$, we show \begin{eqnarray*} γ_e(G) & \geq & \left(\frac{n}{13(Δ-1)^2}\right)^{\frac{\log_2(Δ-1)+1}{\log_2^2(Δ-1)+\log_2(Δ-1)+1}},\\[3mm] γ_e(G) & \leq & 2^{2{\rm r}-2}\mbox{, and }\\[3mm] γ_e(G) & \leq & \frac{43}{108}(n+2). \end{eqnarray*}