SUMMARY
As a natural variant of domination in graphs, Dankelmann et al. [Domination with exponential decay, Discrete Math. 309 (2009) 5877-5883] introduced 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 SS is a set of vertices of a graph GG, then SS is an exponential dominating set of GG if ?v?S(12)dist(G,S)(u,v)-1=1\sum\limits_{v\in S}\left(\frac{1}{2}\right)^{{\rm dist}_{(G,S)}(u,v)-1}\geq 1 for every vertex uu in V(G)\SV(G)\setminus S, where dist(G,S)(u,v){\rm dist}_{(G,S)}(u,v) is the distance between u?V(G)\Su\in V(G)\setminus S and v?Sv\in S in the graph G-(S\{v})G-(S\setminus \{ v\}). The exponential domination number ?e(G)\gamma_e(G) of GG is the minimum order of an exponential dominating set of GG.In the present paper we study exponential domination in subcubic graphs. Our results are as follows: If GG is a connected subcubic graph of order n(G)n(G), then n(G)6log2(n(G)+2)+4=?e(G)=13(n(G)+2).\frac{n(G)}{6\log_2(n(G)+2)+4}\leq \gamma_e(G)\leq \frac{1}{3}(n(G)+2). For every ?>0\epsilon>0, there is some gg such that ?e(G)=?n(G)\gamma_e(G)\leq \epsilon n(G) for every cubic graph GG of girth at least gg. For every 0<a<23ln(2)0, there are infinitely many cubic graphs GG with ?e(G)=3n(G)ln(n(G))a\gamma_e(G)\leq \frac{3n(G)}{\ln(n(G))^{\alpha}}. If TT is a subcubic tree, then ?e(T)=16(n(T)+2).\gamma_e(T)\geq \frac{1}{6}(n(T)+2). For a given subcubic tree, ?e(T)\gamma_e(T) can be determined in polynomial time. The minimum exponential dominating set problem is APX-hard for subcubic graphs.