## Abstract

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).

Original language | English |
---|---|

Pages (from-to) | 175-189 |

Number of pages | 15 |

Journal | Discrete Mathematics |

Volume | 254 |

Issue number | 1-3 |

DOIs | |

Publication status | Published - 10 Jun 2002 |

Externally published | Yes |

## Keywords

- Bounds
- Restricted domination

## ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics