Toward a Nordhaus-Gaddum Inequality for the Number of Dominating Sets

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 inequailties relate a graph $G$ to its complement $\bar{G}$. In this spirit Wagner proved that any graph $G$ on $n$ vertices satisfies $\partial (G)+\partial (\bar{G})\ge 2^n$ where $\partial (G)$ is the number of dominating sets in a graph $G$. In the same paper he comments that an upper bound for $\partial (G)+\partial (\bar{G})$ among all graphs on $n$ vertices seems to be much more difficult. Here we prove an upper bound on $\partial (G)+\partial (\bar{G})$ and prove that any graph maximizing this sum has minimum degree at least $\lfloor n/2\rfloor -2$ and maximum degree at most $\lfloor n/2\rfloor +1$. We conjecture that the complete balanced bipartite graph maximizes $\partial (G)+\partial (\bar{G})$ and have verified this computationally for all graphs on at most $10$ vertices.

References in corpus (1)

• Extremal regular graphs: independent sets and graph homomorphisms