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

A vertex set \( S \subseteq V(G) \) of a graph \( G \) is a \( 2 \)-dominating set of \( G \) if \( |N(v) \cap S| \geq 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 \( \bar{G} \) is the complement of \( G \), then

$$ \gamma_2(G) + \gamma_2(\bar{G}) \leq n + 2, $$

and this bound is best possible in some sense.