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$;...
Saved in:
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Yaroslavl State University
2025-03-01
|
| Series: | Моделирование и анализ информационных систем |
| Subjects: | |
| Online Access: | https://www.mais-journal.ru/jour/article/view/1914 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849338691977216000 |
|---|---|
| author | Mikhail A. Iordanski |
| author_facet | Mikhail A. Iordanski |
| author_sort | Mikhail A. Iordanski |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-2d847549ce924b0f868ffc3615e22d08 |
| institution | Kabale University |
| issn | 1818-1015 2313-5417 |
| language | English |
| publishDate | 2025-03-01 |
| publisher | Yaroslavl State University |
| record_format | Article |
| series | Моделирование и анализ информационных систем |
| spelling | doaj-art-2d847549ce924b0f868ffc3615e22d082025-08-20T03:44:19ZengYaroslavl State UniversityМоделирование и анализ информационных систем1818-10152313-54172025-03-01321324110.18255/1818-1015-2025-1-32-411426Dominant sets with neighborhood for treesMikhail A. Iordanski0Minin Nizhny Novgorod State Pedagogical University; Lobachevsky State University of Nizhny NovgorodThe 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.https://www.mais-journal.ru/jour/article/view/1914treesdiameterradiusdominating set with neighborhooddominance numbergluing and cloning operations |
| spellingShingle | Mikhail A. Iordanski Dominant sets with neighborhood for trees Моделирование и анализ информационных систем trees diameter radius dominating set with neighborhood dominance number gluing and cloning operations |
| title | Dominant sets with neighborhood for trees |
| title_full | Dominant sets with neighborhood for trees |
| title_fullStr | Dominant sets with neighborhood for trees |
| title_full_unstemmed | Dominant sets with neighborhood for trees |
| title_short | Dominant sets with neighborhood for trees |
| title_sort | dominant sets with neighborhood for trees |
| topic | trees diameter radius dominating set with neighborhood dominance number gluing and cloning operations |
| url | https://www.mais-journal.ru/jour/article/view/1914 |
| work_keys_str_mv | AT mikhailaiordanski dominantsetswithneighborhoodfortrees |