An upper bound on the total restrained domination number of a tree

Johannes H. Hattingh, Elizabeth Jonck, Ernst J. Joubert

Research output: Contribution to journalArticlepeer-review

8 Citations (Scopus)

Abstract

Let G=(V,E) be a graph. A set of vertices 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. The total restrained domination number of G, denoted by γ tr (G), is the smallest cardinality of a total restrained dominating set of G. A support vertex of a graph is a vertex of degree at least two which is adjacent to a leaf. We show that γtr(T)n+2s+\ell-1}{2} where T is a tree of order n≥3, and s and 〈 are, respectively, the number of support vertices and leaves of T. We also constructively characterize the trees attaining the aforementioned bound.

Original languageEnglish
Pages (from-to)205-223
Number of pages19
JournalJournal of Combinatorial Optimization
Volume20
Issue number3
DOIs
Publication statusPublished - Oct 2010

Keywords

  • Domination
  • Restrained
  • Total
  • Trees

ASJC Scopus subject areas

  • Computer Science Applications
  • Discrete Mathematics and Combinatorics
  • Control and Optimization
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'An upper bound on the total restrained domination number of a tree'. Together they form a unique fingerprint.

Cite this