How Large Can the Domination
Numbers of a Graph Be?
A vertex $v$ in a graph $G$ dominates itself as well as its neighbors.
A set $S$ of vertices in $G$ is (1) a dominating set
if every vertex of $G$ is dominated by some vertex of $S$,
(2) an open dominating set if every vertex of $G$
is dominated by a vertex of $S$ distinct from itself, and (3) a double
dominating
set if every vertex of $G$ is dominated by at least two distinct vertices
of $S$. The minimum cardinality
of a set $S$ satisfying (1), (2), and (3), respectively, is
the domination number, open domination number, and double domination number
of
$G$, respectively. We consider the problem of determining the maximum value
of each of these domination numbers among all graphs of a given order and
size.