Abstract :
The k-restricted domination number of a graph G is the smallest integer dk such that given any subset U of k vertices of G, there exists a dominating set of G of cardinality at most dk 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 dk⩽(q+2k+1)/3 for all connected graphs of size q and minimum degree at least 2. For k⩾1, we show that dk⩽(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).
