Graphs with large restrained domination number Original Research Article

Let G = (V, E) be a graph. A set S ⊆ 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 restrained domination number of G, denoted by γr(G), is the minimum cardinality of a restrained dominating set of G. Domke et al., submitted [3] showed that if a connected graph G of order n has minimum degree at least 2 and is not one of eight exceptional graphs, then γr(G) ⩽ (n − 1)/2. In this paper, we characterise those graphs of order n which are edge-minimal with respect to satisfying G connected, δ(G) ⩾ 2 and γr(G) ⩾ (n − 1)/2.