On graphs having equal domination and codomination numbers (Q2785713)

The domination number \(\gamma (G)\) of a simple graph is the minimum number of vertices in a dominating set of vertices, i.e. a set of vertices which are together adjacent to all other vertices; the codomination number \(\overline\gamma (G)\) is \(\gamma (\overline G)\). Theorem 1: If \(G\) has no isolates and \(\gamma= \overline \gamma\), then either \(\gamma= \overline \gamma=2\), or \(G\) and its complement both have diameter 2. Theorem 2: If \(G\) and \(\overline{G}\) are connected, then \(\gamma= \overline \gamma=2\) iff either (1) each of \(G\), \(\overline G\) has diameter 3, 4 or 5; or (2) each of \(G\), \(\overline G\) has diameter 2 and a vertex with an isolate in its link. Theorems 3 and 4 respectively characterize trees and cubic graphs in which \(\gamma= \overline \gamma\). Theorem 5: If \(G\) has \(\gamma= \overline \gamma \geq 3\), then \(G\) contains \(C_4\). Theorem 6: If \(G\) is an \(r\)-regular graph for which \(\gamma= \overline \gamma\geq 3\), then \(\gamma= \overline\gamma \leq {r+3\over 2}\). For any nonempty set \(X\) of vertices, \(N_X= \{y\mid y\in \bigcap_{x\in X} N(x)-X\};\) \(n_X=|N_X |\). Theorem 7: If \(\gamma= \overline\gamma \geq 2\), then, for any set \(X\) of \(t\geq 1\) vertices, \(n_X\geq (\gamma-1)^2 -t(\gamma-1) +1\). From the authors' summary: ``The characterization of graphs for which \(\gamma= \overline \gamma\geq 3\) remains an open problem.'' The paper concludes with a construction, for any \(k\geq 3\), of graphs with \(\gamma= \overline \gamma=k\).