Dominating Sets with Neighborhoods for Trees

Subset $$V{\kern 1pt} ' \subset V(G)$$ is called a $$\varepsilon $$ -dominating set of vertices of graph $$G$$ with neighborhood $$\varepsilon $$ if for any vertex $$v \in V\backslash V{\kern 1pt} '$$ there is vertex $$u \in V{\kern 1pt} '$$ such that the length of the shortest path connecting these vertices $$~d\left( {u,v{\;}} \right)~\,\, \leqslant \,\,\varepsilon $$ ; $${{\delta }_{\varepsilon }}(G)$$ is the number of vertices in the minimal $$\varepsilon $$ -dominating set; $${{\delta }_{\varepsilon }}(G) = 1$$ for $$~r\left( G \right)~~~ \leqslant \varepsilon \leqslant d\left( G \right)$$ ; for $$\varepsilon < r(G)$$ the numbers $${{\delta }_{\varepsilon }}(G) > 1$$ , but the calculation of $${{\delta }_{1}}(G) = \delta (G)$$ is an NP‑complete problem. This paper considers class of trees $$t_{d}^{\rho }$$ of diameter $$d$$ whose degrees of all internal vertices are equal to $$\rho $$ . Constructive descriptions of trees $$t \in t_{d}^{\rho }$$ are given. Procedures are developed for computing the values of $${{\delta }_{\varepsilon }}(t)$$ in the range $$~~1 \leqslant \varepsilon < r\left( t \right)$$ . Asymptotic estimates are established for $${{\delta }_{\varepsilon }}(t)$$ and their proportion of the total number of vertices in $$t \in t_{d}^{\rho }$$ as $$d \to \infty $$ . Computational examples are given.