Nordhaus-Gaddum inequalities for domination in graphs (Q1923485)

A subset \(D\) of the vertex set \(V(G)\) of a graph \(G\) is called doubly dominating, if each vertex \(x\) of \(G\) either is in \(D\) and is adjacent to at least one other vertex of \(D\), or is adjacent to at least two vertices of \(D\). The minimum number of vertices of a doubly dominating set is the double domination number \(\text{dd} (G)\) of \(G\). The paper begins by a survey of results of other authors which concern results of Nordhaus-Gaddum type for various domination parameters. Then four theorems are proved. The first theorem is of Nordhaus-Gaddum type and holds for graphs without isolated vertices; it says that \(6 \leq \text{dd} (G) + \text{dd} (\overline G) \leq 2n\), and \(9 \leq \text{dd} (G) \cdot \text{dd} (\overline G) \leq n^2\), where \(\overline G\) is the complement of \(G\) and \(n\) is the number of vertices of \(G\). The fourth theorem says that if the (usual) domination numbers of \(G\) and \(\overline G\) are at least 5, then \(\text{dd} (G) + \text{dd} (\overline G) \leq n - \Delta + \delta - 1\), where \(\Delta\) is the maximum degree and \(\delta\) is the minimum degree of \(G\). Also the remaining theorems are in the form of inequalities. A conjecture is suggested.