On equality in an upper bound for the restrained and total domination numbers of a graph

Peter Dankelmann, David Day, Johannes H. Hattingh, Michael A. Henning, Lisa R. Markus, Henda C. Swart

Research output: Contribution to journalArticlepeer-review

21 Citations (Scopus)

Abstract

Let G = (V, E) be a graph. A set S ⊆ V is a restrained dominating set (RDS) if every vertex not in S is adjacent to a vertex in S and to a vertex in V {minus 45 degree rule} S. The restrained domination number of G, denoted by γr (G), is the minimum cardinality of an RDS of G. A set S ⊆ V is a total dominating set (TDS) if every vertex in V is adjacent to a vertex in S. The total domination number of a graph G without isolated vertices, denoted by γt (G), is the minimum cardinality of a TDS of G. Let δ and Δ denote the minimum and maximum degrees, respectively, in G. If G is a graph of order n with δ ≥ 2, then it is shown that γr (G) ≤ n - Δ, and we characterize the connected graphs with δ ≥ 2 achieving this bound that have no 3-cycle as well as those connected graphs with δ ≥ 2 that have neither a 3-cycle nor a 5-cycle. Cockayne et al. [Total domination in graphs, Networks 10 (1980) 211-219] showed that if G is a connected graph of order n ≥ 3 and Δ ≤ n - 2, then γt (G) ≤ n - Δ. We further characterize the connected graphs G of order n ≥ 3 with Δ ≤ n - 2 that have no 3-cycle and achieve γt (G) = n - Δ.

Original languageEnglish
Pages (from-to)2845-2852
Number of pages8
JournalDiscrete Mathematics
Volume307
Issue number22
DOIs
Publication statusPublished - 28 Oct 2007
Externally publishedYes

Keywords

  • Restrained domination
  • Total domination

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'On equality in an upper bound for the restrained and total domination numbers of a graph'. Together they form a unique fingerprint.

Cite this