\input zb-basic
\input zb-ioport
\iteman{io-port 06046529}
\itemau{Couturier, Jean-Fran\c{c}ois; Heggernes, Pinar; van't Hof, Pim; Kratsch, Dieter}
\itemti{Minimal dominating sets in graph classes: Combinatorial bounds and enumeration.}
\itemso{Bielikov\'a, M\'aria (ed.) et al., SOFSEM 2012: Theory and practice of computer science. 38th conference on current trends in theory and practice of computer science, \v{S}pindler{\uu}v Ml\'yn, Czech Republic, January 21--27, 2012. Proceedings. Berlin: Springer (ISBN 978-3-642-27659-0/pbk). Lecture Notes in Computer Science 7147, 202-213 (2012).}
\itemab
Summary: The maximum number of minimal dominating sets that a graph on $n$ vertices can have is known to be at most $1.7159^{n }$. This upper bound might not be tight, since no examples of graphs with $1.5705^{n }$ or more minimal dominating sets are known. For several classes of graphs, we substantially improve the upper bound on the maximum number of minimal dominating sets in graphs on $n$ vertices. In some cases, we provide examples of graphs whose number of minimal dominating sets exactly matches the proved upper bound for that class, thereby showing that these bounds are tight. For all considered graph classes, the upper bound proofs are constructive and can easily be transformed into algorithms enumerating all minimal dominating sets of the input graph.
\itemrv{~}
\itemcc{}
\itemut{}
\itemli{doi:10.1007/978-3-642-27660-6\_17}
\end