Подмножество $V' \subset V(G)$ образует $\varepsilon$-доминирующее множество графа G, если для любой вершины $v \in V \backslash V'$ найдется вершина $u \in V'$ такая, что длина кратчайшей цепи, соединяющей эти вершины $d(v,u)\leqslant \varepsilon$; $\delta_{\varepsilon}(G)$ — число вершин в минимальном $\varepsilon$-доминирующем множестве; $\delta_{\varepsilon}(G) = 1$ при $r(G)\leqslant \varepsilon \leqslant d(G)$; для $ \varepsilon < r(G)$ числа $\delta_{\varepsilon}(G) > 1$, вычисление $\delta_{1}(G)=\delta(G)$ является NP-полной задачей. В работе рассматривается класс деревьев $t_{d}^{\rho}$ диаметра $d$, степени внутренних вершин которых равны $\rho$. Приводятся конструктивные описания деревьев $t \in t_{d}^{\rho}$. Разработаны процедуры вычисления значений $\delta_{\varepsilon}(t)$ в диапазоне $1\leqslant \varepsilon < r (t)$. Установлены асимптотические оценки для $\delta_{\varepsilon}(t)$ и их доли от общего числа вершин деревьев $t \in t_{d}^{\rho}$ при $d \to \infty$. Приводятся вычислительные примеры.
The subset $V' \subset V(G)$ forms a dominant set of vertices of the graph $G$ with a neighborhood $ \varepsilon$ if for any vertex $v \in V \backslash V'$ there is a vertex $u \in V'$ such that the length of the shortest chain connecting these vertices $d(v,u)\leqslant \varepsilon$; $\delta_{\varepsilon}(G)$ is the number of vertices in the minimal $\varepsilon$-dominating set; $\delta_{\varepsilon}(G) = 1$ for $r(G)\leqslant \varepsilon \leqslant d(G)$; for $ \varepsilon < r(G)$ the numbers $\delta_{\varepsilon}(G) > 1$, but the calculation of $\delta_{1}(G)=\delta(G)$ is an NP-complete problem. The 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 for calculating the values $\delta_{\varepsilon}(t)$ in the range $1\leqslant \varepsilon < r (t)$ have been developed. Asymptotic estimates for $\delta_{\varepsilon}(t)$ and their share of the total number of vertices $t \in t_{d}^{\rho}$ are set at $d \to \infty$. Computational examples are given.
The authors declare that there are no conflicts of interest present.