Exponential domination in subcubic graphs (Q504979): Difference between revisions

Summary: As a natural variant of domination in graphs, \textit{P. Dankelmann} et al. [Discrete Math. 309, No. 19, 5877--5883 (2009; Zbl 1191.05070)] 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 \(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)^{\mathrm{dist}_{(G,S)}(u,v)-1}\geq 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\).{ }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}\leq \gamma_e(G)\leq \frac{1}{3}(n(G)+2). \] For every \(\varepsilon0\), there is some \(g\) such that \(\gamma_e(G)\leq \varepsilon 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)\leq \frac{3n(G)}{\ln(n(G))^{\alpha}}\). If \(T\) is a subcubic tree, then \(\gamma_e(T)\geq \frac{1}{6}(n(T)+2).\) 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.