A Nordhaus-Gaddum-Type Result for the $2$-Domination Number Lutz Volkmann

Abstract

A vertex set $S\subseteq V(G)$ of a graph $G$ is a $2$-dominating set of $G$ if $|N(v)\cap S|\ge 2$ for every vertex $v\in (V(G)–S)$, where $N(v)$ is the neighborhood of $v$. The $2$-domination number ${\gamma }_2(G)$ of graph $G$ is the minimum cardinality among the $2$-dominating sets of $G$. In this paper, we present the following Nordhaus-Gaddum-type result for the $2$-domination number. If $G$ is a graph of order $n$, and $\overline{G}$ is the complement of $G$, then

$${\gamma }_2(G)+{\gamma }_2(\overline{G})\le n+2,$$

and this bound is best possible in some sense.