Restrained domination in graphs (Q1301655)

In this paper, we initiate the study of a variation of standard domination, namely restrained domination. Let \(G=(V,E)\) be a graph. A restrained dominating set is a set \(S\subseteq V\) where every vertex in \(V-S\) is adjacent to a vertex in \(S\) as well as another vertex in \(V-S\). The restrained domination number of \(G\), denoted by \(\gamma_{\text{r}}(G)\), is the smallest cardinality of a restrained dominating set of \(G\). We determine best possible upper and lower bounds for \(\gamma_{\text{r}}(G)\), characterize those graphs achieving these bounds and find best possible upper and lower bounds for \(\gamma_{\text{r}}(G)+\gamma_{\text{r}}(\overline G)\), where \(G\) is a connected graph. Finally, we give a linear algorithm for determining \(\gamma_{\text{r}}(T)\) for any tree and show that the decision problem for \(\gamma_{\text{r}}(G)\) is NP-complete even for bipartite and chordal graphs.