Bounds on the 2-domination number

Abstract

In a graph $G$, a set $D\subseteq V(G)$ is called 2-dominating set if each vertex not in $D$ has at least two neighbors in $D$. The 2-domination number ${\gamma }_2(G)$ is the minimum cardinality of such a set $D$. We give a method for the construction of 2-dominating sets, which also yields upper bounds on the 2-domination number in terms of the number of vertices, if the minimum degree $\delta (G)$ is fixed. These improve the best earlier bounds for any $6\le \delta (G)\le 21$. In particular, we prove that ${\gamma }_2(G)$ is strictly smaller than $n/2$, if $\delta (G)\ge 6$. Our proof technique uses a weight-assignment to the vertices where the weights are changed during the procedure.

20 pages