Restrained domination in graphs
type: Item
instance of: scholarly article
title: Restrained domination in graphs
zbMATH Open document ID: 1114.05303
DOI: 10.1016/S0012-365X(99)00016-3
author: Gayla S. Domke
author: Johannes H. Hattingh
author: L. R. Markus
author: Stephen T. Hedetniemi
author: Renu C. Laskar
published in: Discrete Mathematics
publication date: 1999-09-12T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 1334477
MaRDI profile type: Publication
cites work: Q3818315
cites work: Q4198056
cites work: Q5632603
cites work: On connected cutfree domination in graphs
cites work: On Complementary Graphs
cites work: Q3822197
description: scientific article; zbMATH DE number 1334477