Geodesic
On the Number of Minimum Dominating Sets in Trees
Matematičeskie zametki, Tome 113 (2023) no. 4, pp. 577-595

Voir la notice de l'article provenant de la source Math-Net.Ru

The class of trees in which the degree of each vertex does not exceed an integer $d$ is considered. It is shown that, for $d=4$, each $n$-vertex tree in this class contains at most $(\sqrt{2})^n$ minimum dominating sets (MDS), and the structure of trees containing precisely $(\sqrt{2})^n$ MDS is described. On the other hand, for $d=5$, an $n$-vertex tree containing more than $(1/3) \cdot 1.415^n$ MDS is constructed for each $n \geq 1$. It is shown that each $n$-vertex tree contains fewer than $1.4205^n$ MDS.
Keywords: dominating set, minimum dominating set, tree. 
@article{MZM_2023_113_4_a7,
     author = {D. S. Taletskii},
     title = {On the {Number} of {Minimum} {Dominating} {Sets} in {Trees}},
     journal = {Matemati\v{c}eskie zametki},
     pages = {577--595},
     publisher = {mathdoc},
     volume = {113},
     number = {4},
     year = {2023},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MZM_2023_113_4_a7/}
}
TY  - JOUR
AU  - D. S. Taletskii
TI  - On the Number of Minimum Dominating Sets in Trees
JO  - Matematičeskie zametki
PY  - 2023
SP  - 577
EP  - 595
VL  - 113
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MZM_2023_113_4_a7/
LA  - ru
ID  - MZM_2023_113_4_a7
ER  - 
%0 Journal Article
%A D. S. Taletskii
%T On the Number of Minimum Dominating Sets in Trees
%J Matematičeskie zametki
%D 2023
%P 577-595
%V 113
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MZM_2023_113_4_a7/
%G ru
%F MZM_2023_113_4_a7
D. S. Taletskii. On the Number of Minimum Dominating Sets in Trees. Matematičeskie zametki, Tome 113 (2023) no. 4, pp. 577-595. http://geodesic.mathdoc.fr/item/MZM_2023_113_4_a7/