Dominating Sets with Neighborhoods for Trees

Subset V 1pt ' ⊂ V(G) is called a ε -dominating set of vertices of graph G with neighborhood ε if for any vertex v ∈ V V 1pt ' there is vertex u ∈ V 1pt ' such that the length of the shortest path connecting these vertices ~d( u,v\; )~\,\, \,\,ε ; δ ε(G) is the number of vertices in the minimal ε -dominating set; δ ε(G) = 1 for ~r( G )~~~ ε d( G ) ; for ε < r(G) the numbers δ ε(G) > 1 , but the calculation of δ ₁(G) = δ (G) is an NP‑complete problem. This paper considers class of trees tdρ of diameter d whose degrees of all internal vertices are equal to ρ . Constructive descriptions of trees t ∈ tdρ are given. Procedures are developed for computing the values of δ ε(t) in the range ~~1 ε < r( t ) . Asymptotic estimates are established for δ ε(t) and their proportion of the total number of vertices in t ∈ tdρ as d → ∞ . Computational examples are given.