Bounds on the Maximum Number of Minimum Dominating Sets

Samuel Connolly, Zachary Gabor, Anant Godbole, Bill Kay

Published 2013-08-14Version 1

We use probabilistic methods to find lower bounds on the maximum number, in a graph with domination number \gamma, of dominating sets of size \gamma. We find that we can randomly generate a graph that, w.h.p., is dominated by almost all sets of size \gamma. At the same time, we use a modified adjacency matrix to obtain lower bounds on the number of sets of a given size that do not dominate a graph on n vertices