Hostname: page-component-586b7cd67f-r5fsc Total loading time: 0 Render date: 2024-11-28T09:53:32.269Z Has data issue: false hasContentIssue false
  • English
  • Français

Minimal 2-dominating sets in trees∗

Published online by Cambridge University Press:  08 July 2013

Marcin Krzywkowski
Marcin Krzywkowski*
Affiliation:
Faculty of Electronics, Telecommunications and Informatics, Gdańsk University of Technology, Narutowicza 11/12, 80–233 Gdańsk, Poland.. [email protected]
Get access

Abstract

We provide an algorithm for listing all minimal 2-dominating sets of a tree of ordern in time 𝒪(1.3248n). This implies that every tree has at most1.3248n minimal 2-dominating sets. We also show that thisbound is tight.

Keywords

Domination2-dominationminimal 2-dominating settreecountingexact exponential algorithmlisting algorithm
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 47 , Issue 3 , July 2013 , pp. 235 - 240
Copyright
© EDP Sciences 2013

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

A. Björklund and T. Husfeldt, Inclusion-exclusion algorithms for counting set partitions. Proc. of FOCS (2006) 575–582.
Blidia, M., Favaron, O. and Lounes, R., Locating-domination, 2-domination and independence in trees. Australas. J. Combin. 42 (2008) 309–316. Google Scholar
Bród, D. and Skupień, Z., Trees with extremal numbers of dominating sets. Australas. J. Combin. 35 (2006) 273–290. Google Scholar
Bród, D., Włoch, A. and Włoch, I., On the number of minimal dominating sets including the set of leaves in trees. Internat. J. Contemporary Math. Sci. 4 (2009) 1739–1748. Google Scholar
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.
Eppstein, D., Small maximal independent sets and faster exact graph coloring, J. Graph Algorithms Appl. 7 (2003) 131–140. CrossRefGoogle Scholar
J. Fink and M. Jacobson, n-domination in graphs, Graph Theory with Applications to Algorithms and Computer Science. Wiley, New York (1985) 282−300.
F. Fomin, F. Grandoni, A. Pyatkin and A. Stepanov, Combinatorial bounds via measure and conquer: bounding minimal dominating sets and applications. ACM Transactions on Algorithms, vol. 5, article 9 (2009).
F. Fomin and D. Kratsch, Exact Exponential Algorithms. Springer, Berlin (2010).
Fujisawa, J., Hansberg, A., Kubo, T., Saito, A., Sugita, M. and Volkmann, L., Independence and 2-domination in bipartite graphs. Australas. J. Combin. 40 (2008) 265–268. Google Scholar
T. Haynes, S. Hedetniemi and P. Slater, Fundamentals of Domination in Graphs. Marcel Dekker, New York (1998).
T. Haynes, S. Hedetniemi and P. Slater, Domination in Graphs: Advanced Topics. Marcel Dekker, New York (1998).
M. Kanté, V. Limouzy, A. Mary and L. Nourine, Enumeration of minimal dominating sets and variants, Fundamentals of computation theory. Lect. Notes Comput. Sci., vol. 6914. Springer, Heidelberg (2011) 298–309.
M. Koivisto, 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.
Lawler, E., A note on the complexity of the chromatic number problem. Information Proc. Lett. 5 (1976) 66–67. Google Scholar
Moon, J. and Moser, L., On cliques in graphs. Israel J. Math. 3 (1965) 23–28. Google Scholar
Shaheen, R., Bounds for the 2-domination number of toroidal grid graphs. Internat. J. Comput. Math. 86 (2009) 584–588. Google Scholar
Wilf, H., The number of maximal independent sets in a tree. SIAM J. Algebr. Discrete Methods 7 (1986) 125–130. Google Scholar