Graphs with large restrained domination number

Research output: Contribution to journalArticlepeer-review

30 Citations (Scopus)


Let G=(V,E) be a graph. A set S⊆V is a restrained dominating set if every vertex not in S is adjacent to a vertex in S and to a vertex in V - S. The restrained domination number of G, denoted by γr(G), is the minimum cardinality of a restrained dominating set of G. Domke et al., submitted [3] showed that if a connected graph G of order n has minimum degree at least 2 and is not one of eight exceptional graphs, then γr(G)≤(n-1)/2. In this paper, we characterise those graphs of order n which are edge-minimal with respect to satisfying G connected, δ(G)≥2 and γr(G)≥(n-1)/2.

Original languageEnglish
Pages (from-to)415-429
Number of pages15
JournalDiscrete Mathematics
Publication statusPublished - 28 Feb 1999
Externally publishedYes


  • Bounds
  • Characterisation
  • Restrained domination

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Graphs with large restrained domination number'. Together they form a unique fingerprint.

Cite this