RUS  ENG
Full version
JOURNALS // Modelirovanie i Analiz Informatsionnykh Sistem // Archive

Model. Anal. Inform. Sist., 2025 Volume 32, Number 1, Pages 32–41 (Mi mais839)

Discrete mathematics in relation to computer science

Dominant sets with neighborhood for trees

M. A. Iordanskiab

a Lobachevsky State University of Nizhny Novgorod, Nizhny Novgorod, Russia
b Minin Nizhny Novgorod State Pedagogical University, Nizhny Novgorod, Russia

Abstract: 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.

Keywords: trees, diameter, radius, dominating set with neighborhood, dominance number, gluing and cloning operations.

UDC: 519.17

MSC: 05C69

Received: 18.12.2024
Revised: 02.02.2025
Accepted: 12.02.2025

DOI: 10.18255/1818-1015-2025-1-32-41



© Steklov Math. Inst. of RAS, 2025