Nordhaus-Gaddum results for restrained domination and total restrained domination in graphs

Johannes H. Hattingh, Elizabeth Jonck, Ernst J. Joubert, Andrew R. Plummer

Research output: Contribution to journalArticlepeer-review

34 Citations (Scopus)

Abstract

Let G = (V, E) be a graph. A set S ⊆ V is a total restrained dominating set if every vertex is adjacent to a vertex in S and every vertex of V - S is adjacent to a vertex in V - S. A set S ⊆ V is a restrained dominating set if every vertex in V - S is adjacent to a vertex in S and to a vertex in V - S. The total restrained domination number of G (restrained domination number of G, respectively), denoted by γtr (G) (γr (G), respectively), is the smallest cardinality of a total restrained dominating set (restrained dominating set, respectively) of G. We bound the sum of the total restrained domination numbers of a graph and its complement, and provide characterizations of the extremal graphs achieving these bounds. It is known (see [G.S. Domke, J.H. Hattingh, S.T. Hedetniemi, R.C. Laskar, L.R. Markus, Restrained domination in graphs, Discrete Math. 203 (1999) 61-69.]) that if G is a graph of order n ≥ 2 such that both G and over(G, -) are not isomorphic to P3, then 4 ≤ γr (G) + γr (over(G, -)) ≤ n + 2. We also provide characterizations of the extremal graphs G of order n achieving these bounds.

Original languageEnglish
Pages (from-to)1080-1087
Number of pages8
JournalDiscrete Mathematics
Volume308
Issue number7
DOIs
Publication statusPublished - 6 Apr 2008

Keywords

  • Domination
  • Nordhaus-Gaddum
  • Restrained
  • Total

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'Nordhaus-Gaddum results for restrained domination and total restrained domination in graphs'. Together they form a unique fingerprint.

Cite this