Restricted domination in graphs with minimum degree 2 Original Research Article

The k-restricted domination number of a graph G is the smallest integer image such that given any subset U of k vertices of G, there exists a dominating set of G of cardinality at most image containing U. Hence, the k-restricted domination number of a graph G measures how many vertices are necessary to dominate a graph if an arbitrary set of k vertices must be included in the dominating set. When image, the k-restricted domination number is the domination number. For image, it is known that image for all connected graphs of order n and minimum degree at least 2 (see [M.A. Henning, Restricted domination in graphs, Discrete Math. 254 (2002) 175–189]). In this paper we characterize those graphs of order n which are edge-minimal with respect to satisfying the conditions of connected, minimum degree at least two, and image. These results extend results due to McCuaig and Shepherd [Domination in graphs with minimum degree two, J. Graph Theory 13 (1989) 749–762].