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.