Restrained and total restrained domination in cographs (Q2151385)

Let \(G\) be a simple and undirected graph with vertex set \(V(G)\) and edge set \(E(G)\). For \(S\subseteq V(G)\), let \(S^c=V(G)-S\). A set \(S \subseteq V(G)\) is a restrained dominating set of \(G\) if each vertex in \(S^c\) is adjacent to at least one vertex in \(S\) and at least one vertex in \(S^c\). For a graph \(G\) with no isolated vertex, a set \(S\subseteq V(G)\) is a total restrained dominating set of \(G\) if \(S\) is a restrained dominating set of \(G\) and each vertex in \(S\) is adjacent to at least one vertex in \(S\). The restrained domination number \(\gamma_{\mathrm{r}}(G)\) (the total restrained domination number \(\gamma_{\mathrm{tr}}(G)\), respectively) of \(G\) is the minimum cardinality among all restrained dominating sets (among all total restrained dominating sets, respectively) of \(G\). For any connected graph \(G\) of order \(n\), it is known that \(1\le \gamma_{\mathrm{r}}(G) \le n\) and \(2\le \gamma_{\mathrm{tr}}(G)\le n\). \textit{G. S. Domke} et al. [Discrete Math. 203, No. 1--3, 61--69 (1999; Zbl 1114.05303)] characterize (connected) graphs \(G\) of order \(n\) satisfying \(\gamma_{\mathrm{r}}(G)=n\), \(\gamma_{\mathrm{r}}(G)=n-2\) and \(\gamma_{\mathrm{r}}(G)=1\), respectively, and show that determining \(\gamma_{\mathrm{r}}(G)\) for a general graph \(G\) is an NP-complete problem, and they provide a linear time algorithm to compute \(\gamma_{\mathrm{r}}(T)\) for any tree \(T\). \textit{D. Ma} et al. [Czech. Math. J. 55, No. 1, 165--173 (2005; Zbl 1081.05086)] show that determining \(\gamma_{\mathrm{tr}}(G)\) for a general graph \(G\) is an NP-complete problem. \textit{X. Chen} et al. [Comput. Math. Appl. 62, No. 8, 2892--2898 (2011; Zbl 1231.05196)] characterize connected graphs \(G\) of order \(n\ge4\) satisfying \(\gamma_{\mathrm{tr}}(G)\) equals \(n\) and \(n-2\), respectively. A graph \(G\) is a cograph (or a complement-reducible graph) if \(G\) can be constructed from isolated vertices by disjoint union and graph join operations. The authors of the present paper determine \(\gamma_{\mathrm{r}}(G+H)\) and \(\gamma_{\mathrm{tr}}(G+H)\), respectively, where \(G+H\) denotes the join of two cographs \(G\) and \(H\). They also provide a linear time algorithm for finding the restrained domination number and the total restrained domination number, respectively, of cographs via simple bottom-up calculations on the cotrees. For the entire collection see [Zbl 1490.68034].