Article ID Journal Published Year Pages File Type
4648836 Discrete Mathematics 2007 8 Pages PDF
Abstract

Let G=(V,E)G=(V,E) be a graph. A set S⊆VS⊆V is a total restrained dominating set if every vertex is adjacent to a vertex in S   and every vertex of V-SV-S is adjacent to a vertex in V-SV-S. The total restrained domination number of G  , denoted by γtr(G)γtr(G), is the smallest cardinality of a total restrained dominating set of G. We show that if T is a tree of order n  , then γtr(T)⩾n+22. Moreover, we show that if T   is a tree of order n≡0mod4, then γtr(T)⩾n+22+1. We then constructively characterize the extremal trees T of order n achieving these lower bounds.

Keywords
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , , ,