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 language | English |
---|---|
Pages (from-to) | 205-223 |
Number of pages | 19 |
Journal | Journal of Combinatorial Optimization |
Volume | 20 |
Issue number | 3 |
DOIs | |
Publication status | Published - 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