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/

[1] A. E. Brouwer, The Number of Dominating Sets of a Finite Graph is Odd, , 2009 http://www.win.tue.nl/~aeb/preprints/domin2.pdf

[2] D. Bród, Z. Skupień, “Trees with extremal numbers of dominating sets”, Australas. J. Combin., 35 (2006), 273–290 | MR

[3] S. Wagner, “A note on the number of dominating sets of a graph”, Util. Math., 92 (2013), 25–31 | MR | Zbl

[4] D. S. Taletskii, “Trees with extremal numbers of $k$-dominating sets”, Discrete Math., 345:1 (2022) | DOI | MR | Zbl

[5] G. Gunther, B. Hartnell, L. R. Markus, D. Rall, “Graphs with unique minimum dominating sets”, Proceedings of the Twenty-Fifth Southeastern International Conference on Combinatorics, Graph Theory and Computing (Boca Raton, FL, 1994), Congr. Numer., 101, 1994, 55–63 | MR

[6] A. Bień, “Properties of gamma graphs of trees”, Presentation at the 17th Workshop on Graph Theory Colourings, Independence and Domination (CID 2017), Piechowice, Poland

[7] J. Alvarado, S. Dantas, E. Mohr, D. Rautenbach, “On the maximum number of minimum dominating sets in forests”, Discrete Math., 342:4 (2018), 934–942 | DOI | MR