Menu
Let \(G = (V,E)\) be a graph. A set \(S \subseteq V\) is a dominating set if every vertex not in \(S\) is adjacent to a vertex in \(S\). Furthermore, a set \(S \subseteq V\) is a restrained dominating set if every vertex not in \(S\) is adjacent to a vertex in \(S\) and to a vertex in \(V – S\). The domination number of \(G\), denoted by \(\gamma(G)\), is the minimum cardinality of a dominating set, while the restrained domination number of \(G\), denoted by \(\gamma_r(G)\), is the minimum cardinality of a restrained dominating set of \(G\).
We show that if a connected graph \(G\) of order \(n\) has minimum degree at least \(2\) and is not one of eight exceptional graphs, then \(\gamma_r(G) \leq (n – 1)/2\). We show that if \(G\) is a graph of order \(n\) with \(\delta = \delta(G) \geq 2\), then \(\gamma_r(G) \leq n(1 + (\frac{1}{\delta})^\frac{\delta}{\delta-1} – (\frac{1}{\delta})^\frac{1}{\delta-1})\).