On the Number of Minimum Total Dominating Sets in Trees

被引：0

作者：

Taletskii D.S. ^{[1
,2
]}

机构：

[1] National Research University Higher School of Economics, Nizhny NovgorodBranch, Nizhny Novgorod

[2] Lobachevsky State University of Nizhny Novgorod, Nizhny Novgorod

来源：

Journal of Applied and Industrial Mathematics | 2023年 / 17卷 / 01期

基金：

俄罗斯科学基金会;

关键词：

2-caterpillar; extremal combinatorics; minimum total dominating set; tree;

D O I：

10.1134/S1990478923010234

中图分类号：

O144 [集合论]; O157 [组合数学（组合学）];

学科分类号：

070104 ;

摘要：

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 atleast one vertex of D . In this paper we obtain a sharp upper bound for the number of MTDSs inthe class of n -vertex 2-caterpillars. We also show that for all (Formula presented.) every n -vertex tree has less than $$(sqrt {2})^n$$ MTDSs. © 2023, Pleiades Publishing, Ltd.

引用

页码：213 / 224

页数：11

共 7 条

[1]

Brod D., Skupien Z., Trees with extremal numbers of dominating sets, Australas. J. Combin., 35, pp. 273-290, (2006)

[2]

Krzywkowski M., Wagner S., Graphs with few total dominating sets, Discrete Math., 341, 4, pp. 997-1009, (2018)

[3]

Bien A., Properties of gamma graphs of trees, 17Th Workshop on Graph Theory Colourings, Independence and Domination (CID 2017), (2017)

[4]

Alvarado J., Dantas S., Mohr E., Rautenbach D., On the maximum number of minimum dominating sets in forests, Discrete Math., 342, 4, pp. 934-942, (2018)

[5]

Taletskii D.S., Trees with extremal numbers of $$k$$ -dominating sets, Discrete Math., 345, 1, (2022)

[6]

Rote G., Minimal Dominating Sets in a Tree: Counting, Enumeration, and Extremal Results, (2019)

[7]

Henning M.A., Mohr E., Rautenbach D., On the maximum number of minimum total dominating sets in forests, Discrete Math. Theor. Comput. Sci., 21, 3, (2019)

← 1 →