Exponential Domination in Subcubic Graphs

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$. In the present paper we study exponential domination in subcubic graphs. Our results are as follows: If $G$ is a connected subcubic graph of order $n(G)$, then $$\frac{n(G)}{6{\log }_2(n(G)+2)+4}\le {\gamma }_e(G)\le \frac{1}{3}(n(G)+2)\mathrm{.}$$ For every $ϵ>0$, there is some $g$ such that ${\gamma }_e(G)\le ϵn(G)$ for every cubic graph $G$ of girth at least $g$. For every $0<\alpha <\frac{2}{3\ln (2)}$, there are infinitely many cubic graphs $G$ with ${\gamma }_e(G)\le \frac{3n(G)}{\ln (n(G){)}^{\alpha }}$. If $T$ is a subcubic tree, then ${\gamma }_e(T)\ge \frac{1}{6}(n(T)+2)\mathrm{.}$ For a given subcubic tree, ${\gamma }_e(T)$ can be determined in polynomial time. The minimum exponential dominating set problem is APX-hard for subcubic graphs.