A note on Nordhaus-Gaddum inequalities for domination. (Q1421486)

Let \(D\) be a subset of the vertex set \(V\) of a graph \(G\) and let \(k\) be a positive integer. For each \(x\in V-D\) let there exist \(k\) vertices \(y_1,\dots,y_k\) adjacent to \(x\). If \(k=1\) then \(D\) is called a dominating set in \(G\), if \(k=2\) a double dominating set in \(G\) and if \(k\geq 3\) a \(k\)-dominating set in \(G\). If for each \(x\in V\) there exists \(y\in D\) adjacent to \(x\), then \(D\) is called a total dominating set in \(G\). The minimum number of vertices of a dominating set in \(G\) is called the domination number \(\gamma(G)\) of \(G\). Analogously the double domination number \(\gamma_2(G)\), the \(k\)-domination number \(\gamma_k(G)\) and the total domination number \(\gamma_t(G)\) of \(G\) are defined. The paper brings some Nordhaus-Gaddun type results. (The symbols \(\overline G\), \(\delta(G)\) and \(\Delta(G)\) denote the complement of \(G\), the minimum degree and the maximum degree of \(G\).) If \(k\geq 1\), \(\gamma(G)\geq k+2\), and \(\gamma (\overline G)\geq k+ 2\), then \(\gamma_k(G)+ \gamma_k (\overline G)\leq n-\Delta(G)+ \delta (G)-1\). If \(\gamma (G)\geq 4\) and \(\gamma (\overline G)\geq 4\), then \(\gamma_2(G) +\gamma_2 (\overline G)\leq n-\Delta(G) +\delta(G)-1\leq n-1\). If \(\gamma(G)\geq 3\) and \(\gamma(\overline G)\geq 3\), then \(\gamma_t(G)+ \gamma_t(\overline G)\leq n-\Delta(G)+\delta(G)-1\).