## 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, it is known that d_{k} ≤ (2 n + 3 k) / 5 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 d_{k} = (2 n + 3 k) / 5. These results extend results due to McCuaig and Shepherd [Domination in graphs with minimum degree two, J. Graph Theory 13 (1989) 749-762].

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

Pages (from-to) | 1356-1366 |

Number of pages | 11 |

Journal | Discrete Mathematics |

Volume | 307 |

Issue number | 11-12 |

DOIs | |

Publication status | Published - 28 May 2007 |

Externally published | Yes |

## Keywords

- Bounds
- Minimum degree 2
- Restricted domination

## ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics