Editorial Board
Publishing Ethics
Author Guide
Submission Prepare Your ManuscriptPeer review
Archive
Volume 30, No 1, 2023, P. 110-129
UDC 519.17
D. S. Taletskii
On the number of minimum total dominating sets in trees
Abstract:
The minimum total dominating set (MTDS) of a graph is a vertex subset $D$ of minimum cardinality such that every vertex of the graph is adjacent to at least one vertex of $D$. In this paper we obtain the sharp upper bound for the number of MTDS in the class of $n$-vertex 2-caterpillars. We also show that for all $n \ge 1$ every $n$-vertex tree has less than $(\sqrt{2})^n$ MTDS.
Illustr. 5, bibliogr. 6.
Keywords: extremal combinatorics, tree, 2-caterpillar,minimum total dominating set.
DOI: 10.33048/daio.2023.30.745
Dmitrii S. Taletskii 1,2
1. National Research University “Higher School of Economics”,
25/12 Bolshaya Pechyorskaya Street, 603155 Nizhny Novgorod, Russia
2. Lobachevsky Nizhny Novgorod State University,
23 Gagarin Street, 603950 Nizhny Novgorod, Russia
e-mail: dmitalmail@gmail.com
Received June 16, 2022
Revised October 4, 2022
Accepted October 6, 2022
References
[1] D. Bród and Z. Skupien, Trees with extremal numbers of dominating sets, Australas. J. Comb. 35, 273–290 (2006).[2] M. Krzywkowski and S. Wagner, Graphs with few total dominating sets, Discrete Math. 341 (4), 997–1009 (2018).
[3] A. Bien, Properties of gamma graphs of trees, Colourings, Independence and Domination (Abs. 17th Workshop Graph Theory, Piechowice, Poland, Sept. 17–22, 2017) (Univ. Zielona Góra, Zielona Góra, 2017).
Available at www.cid.uz.zgora.pl/php/pdf_file.php?vid=1046 (accessed Jan. 13, 2023).
[4] J. Alvarado, S. Dantas, E. Mohr, and D. Rautenbach, On the maximum number of minimum dominating sets in forests, Discrete Math. 342 (4), 934–942 (2018).
[5] D. S. Taletskii, Trees with extremal numbers of $k$-dominating sets, Discrete Math. 345 (1), ID 112656, 5 p. (2022).
[6] G. Rote, Minimal dominating sets in a tree: Counting, enumeration, and extremal results (Cornell Univ., Ithaca, NY, 2019) (Cornell Univ. Libr. e-Print Archive, arXiv:1903.04517).
[7] M. A. Henning, E. Mohr, and D. Rautenbach, On the maximum number of minimum total dominating sets in forests, Discrete Math. Theor. Comput. Sci. 21 (3), ID 3, 12 p. (2019).
