Dominant sets with neighborhood for trees
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.
Authors
- Mikhail A. Iordanski
Institutions
- Nizhny Novgorod State Pedagogical University (RU)
- N. I. Lobachevsky State University of Nizhny Novgorod (RU)
Publication Details
- Journal
- Modeling and Analysis of Information Systems
- Published
- 2025-03-22
- DOI
- https://doi.org/10.18255/1818-1015-2025-1-32-41
- Citations
- 1
- Primary Topic
- Advanced Graph Theory Research
- Type
- article
- Field-Weighted Citation Impact
- 1.50