Restrained domination in graphs (Q1301655)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Restrained domination in graphs
scientific article

    Statements

    Restrained domination in graphs (English)
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    12 September 1999
    0 references
    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.
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references