Trees with equal domination and restrained domination numbers

Peter Dankelmann, Johannes H. Hattingh, Michael A. Henning, Henda C. Swart

Research output: Contribution to journalArticlepeer-review

22 Citations (Scopus)

Abstract

Let G = (V, E) be a graph and let S ⊆ V. The set S is a packing in G if the vertices of S are pairwise at distance at least three apart in G. The set 3 is a dominating set (DS) if every vertex in V - S is adjacent to a vertex in S. Further, if every vertex in V - S is also adjacent to a vertex in V - S. then S is a restrained dominating set (RDS). The domination number of G. denoted by γ(G). is the minimum cardinality of a DS of G, while the restrained domination number of G, denoted by γr(G), is the minimum cardinality of a RDS of G. The graph G is γ-excellent if every vertex of G belongs to some minimum DS of G. A constructive characterization of trees with equal domination and restrained domination numbers is presented. As a consequence of this characterization we show that the following statements are equivalent: (i) T is a tree with γ(T) = γr(T); (ii) T is a γ-excellent tree and T ≠ K2; and (iii) T is a tree that has a unique maximum packing and this set is a dominating set of T. We show that if T is a tree of order n with ℓ leaves, then γr(T) ≤ (n + ℓ+ 1)/2, and we characterize those trees achieving equality.

Original languageEnglish
Pages (from-to)597-607
Number of pages11
JournalJournal of Global Optimization
Volume34
Issue number4
DOIs
Publication statusPublished - Apr 2006
Externally publishedYes

Keywords

  • Domination
  • Domination excellent trees
  • Restrained domination

ASJC Scopus subject areas

  • Computer Science Applications
  • Management Science and Operations Research
  • Control and Optimization
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Trees with equal domination and restrained domination numbers'. Together they form a unique fingerprint.

Cite this