A dominating set in a graph
is a set
of vertices such
that every vertex of
is either in
or is
adjacent to a vertex in
.
Nordhaus–Gaddum inequalities relate a graph
to its complement
. In this spirit Wagner
proved that any graph
on
vertices
satisfies
, where
is the number of
dominating sets in a graph
.
In the same paper he commented that proving an upper bound for
among all
graphs on
vertices seems to be much more difficult. Here we prove an upper bound on
and
prove that any graph maximizing this sum has minimum degree at least
and maximum
degree at most
.
We conjecture that the complete balanced bipartite graph maximizes
and have verified this computationally for all graphs on at most
vertices.
