#### Vol. 12, No. 7, 2019

 Recent Issues
 The Journal About the Journal Editorial Board Subscriptions Editors’ Interests Scientific Advantages Submission Guidelines Submission Form Ethics Statement Editorial Login ISSN: 1944-4184 (e-only) ISSN: 1944-4176 (print) Author Index Coming Soon Other MSP Journals
Toward a Nordhaus–Gaddum inequality for the number of dominating sets

### Lauren Keough and David Shane

Vol. 12 (2019), No. 7, 1175–1181
##### Abstract

A dominating set in a graph $G$ is a set $S$ of vertices such that every vertex of $G$ is either in $S$ or is adjacent to a vertex in $S$. Nordhaus–Gaddum inequalities relate a graph $G$ to its complement $\overline{G}$. In this spirit Wagner proved that any graph $G$ on $n$ vertices satisfies $\partial \left(G\right)+\partial \left(\overline{G}\right)\ge {2}^{n}$, where $\partial \left(G\right)$ is the number of dominating sets in a graph $G$. In the same paper he commented that proving an upper bound for $\partial \left(G\right)+\partial \left(\overline{G}\right)$ among all graphs on $n$ vertices seems to be much more difficult. Here we prove an upper bound on $\partial \left(G\right)+\partial \left(\overline{G}\right)$ and prove that any graph maximizing this sum has minimum degree at least $⌊n∕2⌋-2$ and maximum degree at most $⌈n∕2⌉+1$. We conjecture that the complete balanced bipartite graph maximizes $\partial \left(G\right)+\partial \left(\overline{G}\right)$ and have verified this computationally for all graphs on at most $10$ vertices.