Restricted domination in graphs

The k-restricted domination number of a graph G is the smallest integer d_k such that given any subset U of k vertices of G, there exists a dominating set of G of cardinality at most d_k 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 k = 0, the k-restricted domination number is the domination number. For k ≥ 1, Sanchis (J. Graph Theory 25 (1997) 139) showed that d_k ≤ (q+2k+1)/3 for all connected graphs of size q and minimum degree at least 2. For k ≥ 1, we show that d_k ≤ (2n + 3k)/5 for all connected graphs of order n and minimum degree at least 2. This bound improves on the Sanchis bound for dense graphs, namely those connected graphs of size q and order n satisfying q > (6n - k - 5)/5. Our bound also extends a result due to McCraig and Shepherd (J. Graph Theory 13 (1989) 749).