Доминирующие множества с окрестностью для деревьев

Аннотация

Подмножество $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$. Приводятся вычислительные примеры.