Restrained domination in trees

Gayla S. Domke, Johannes H. Hattingh, Michael A. Henning, Lisa R. Markus

Research output: Contribution to journalArticlepeer-review

41 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 smallest cardinality of a restrained dominating set of G. We show that if T is a tree of order n, then γr(T)≥[(n + 2)/3]. Moreover, we constructively characterize the extremal trees T of order n achieving this lower bound.

Original languageEnglish
Pages (from-to)1-9
Number of pages9
JournalDiscrete Mathematics
Issue number1-3
Publication statusPublished - 28 Jan 2000
Externally publishedYes

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Restrained domination in trees'. Together they form a unique fingerprint.

Cite this