Bounds on the maximum number of minimum dominating sets

Given a graph with domination number γγ, we find bounds on the maximum number of minimum dominating sets. First, for γ≥3γ≥3, we obtain lower bounds on the number of γγ-sets that do not dominate a graph on nn vertices. Then, we show that γγ-fold lexicographic product of the complete graph on n1/γn1/γ vertices has domination number γγ and nγ−O(nγ−1γ) dominating sets of size γγ. Finally, we see that a certain random graph has, with high probability, (i) domination number γγ; and (ii) all but o(nγ)o(nγ) of its γγ-sets being dominating.