We provide an algorithm for listing all minimal 2-dominating sets of a tree of order n in time 𝒪(1.3248n). This implies that every tree has at most 1.3248n minimal 2-dominating sets. We also show that this bound is tight.
@article{ITA_2013__47_3_235_0,
author = {Krzywkowski, Marcin},
title = {Minimal 2-dominating sets in trees},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
volume = {47},
year = {2013},
pages = {235-240},
doi = {10.1051/ita/2013036},
mrnumber = {3103126},
zbl = {1282.05179},
language = {en},
url = {http://dml.mathdoc.fr/item/ITA_2013__47_3_235_0}
}
Krzywkowski, Marcin. Minimal 2-dominating sets in trees. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 47 (2013) pp. 235-240. doi : 10.1051/ita/2013036. http://gdmltest.u-ga.fr/item/ITA_2013__47_3_235_0/
[1] and , Inclusion-exclusion algorithms for counting set partitions. Proc. of FOCS (2006) 575-582.
[2] , and , Locating-domination, 2-domination and independence in trees. Australas. J. Combin. 42 (2008) 309-316. | MR 2445823 | Zbl 1153.05039
[3] and , Trees with extremal numbers of dominating sets. Australas. J. Combin. 35 (2006) 273-290. | MR 2239321 | Zbl 1094.05017
[4] , and , On the number of minimal dominating sets including the set of leaves in trees. Internat. J. Contemporary Math. Sci. 4 (2009) 1739-1748. | MR 2674931 | Zbl 1219.05113
[5] J.-F. Couturier, P. Heggernes, P. van 't Hof and D. Kratsch, Minimal dominating sets in graph classes: combinatorial bounds and enumeration. Proc. of SOFSEM 2012, Lect. Notes Comput. Sci., vol. 7147. Springer-Verlag, Berlin (2012) 202-213. | MR 2958175 | Zbl 1298.05246
[6] , Small maximal independent sets and faster exact graph coloring, J. Graph Algorithms Appl. 7 (2003) 131-140. | MR 2112051 | Zbl 1027.05092
[7] and , n-domination in graphs, Graph Theory with Applications to Algorithms and Computer Science. Wiley, New York (1985) 282−300. | MR 812671 | Zbl 0573.05049
[8] , , and , Combinatorial bounds via measure and conquer: bounding minimal dominating sets and applications. ACM Transactions on Algorithms, vol. 5, article 9 (2009). | MR 2479180
[9] and , Exact Exponential Algorithms. Springer, Berlin (2010). | MR 3234973 | Zbl pre05817382
[10] , , , , and , Independence and 2-domination in bipartite graphs. Australas. J. Combin. 40 (2008) 265-268. | MR 2381434 | Zbl 1147.05052
[11] , and , Fundamentals of Domination in Graphs. Marcel Dekker, New York (1998). | MR 1605684 | Zbl 0883.00011
[12] , and , Domination in Graphs: Advanced Topics. Marcel Dekker, New York (1998). | MR 1605685 | Zbl 0883.00011
[13] , , and , Enumeration of minimal dominating sets and variants, Fundamentals of computation theory. Lect. Notes Comput. Sci., vol. 6914. Springer, Heidelberg (2011) 298-309. | MR 2886915 | Zbl pre05940784
[14] , An 𝒪(2n) algorithm for graph coloring and other partitioning problems via inclusion-exclusion. Proc. 47th Annual IEEE Symposium on Foundations of Comput. Sci. (FOCS 2006), IEEE (2006) 583-590.
[15] , A note on the complexity of the chromatic number problem. Information Proc. Lett. 5 (1976) 66-67. | MR 464675 | Zbl 0336.68021
[16] and , On cliques in graphs. Israel J. Math. 3 (1965) 23-28. | MR 182577 | Zbl 0144.23205
[17] , Bounds for the 2-domination number of toroidal grid graphs. Internat. J. Comput. Math. 86 (2009) 584-588. | MR 2514154 | Zbl 1162.05036
[18] , The number of maximal independent sets in a tree. SIAM J. Algebr. Discrete Methods 7 (1986) 125-130. | MR 819714 | Zbl 0584.05024