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≥1 every n-vertex tree has less than (√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).
