Restricted domination in graphs with minimum degree 2

Research output: Contribution to journalArticlepeer-review


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, it is known that dk ≤ (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 dk = (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 languageEnglish
Pages (from-to)1356-1366
Number of pages11
JournalDiscrete Mathematics
Issue number11-12
Publication statusPublished - 28 May 2007
Externally publishedYes


  • Bounds
  • Minimum degree 2
  • Restricted domination

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Restricted domination in graphs with minimum degree 2'. Together they form a unique fingerprint.

Cite this