Bounding the number of minimal dominating sets: A measure and conquer approach

We show that the number of minimal dominating sets in a graph on n vertices is at most 1.7697(n), thus improving on the trivial O(2(n)/root n) bound. Our result makes use of the measure and conquer technique from exact algorithms, and can be easily turned into an O(1.7697(n)) listing algorithm. Based on this result, we derive an O(2.8805(n)) algorithm for the domatic number problem, and an O(1.5780(n)) algorithm for the minimum-weight dominating set problem. Both algorithms improve over the previous algorithms.