An Upper Bound on the Restrained Domination Number of Graphs

Abstract

Let \(G = (V,E)\) be a graph. A set \(S \subseteq V\) is called a restrained dominating set of \(G\) if every vertex not in \(S\) is adjacent to a vertex in \(S\) and to a vertex in \(V – S\). The restrained domination number of \(G\), denoted by \(\gamma_r(G)\), is the minimum cardinality of a restrained dominating set of \(G\). In this paper, we establish an upper bound on \(\gamma_r(G)\) for a connected graph \(G\) by the probabilistic method.