Minimal 2-dominating sets in trees∗
Faculty of Electronics, Telecommunications and Informatics, Gdańsk University
of Technology, Narutowicza 11/12, 80–233 Gdańsk, Poland.
Accepted: 30 April 2013
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.
Mathematics Subject Classification: 05C05 / 05C69 / 05C85 / 68R10 / 68W05
Key words: Domination / 2-domination / minimal 2-dominating set / tree / counting / exact exponential algorithm / listing algorithm
© EDP Sciences 2013