Total restrained domination in trees

被引：24

作者：

Hattingh, Johannes H. ^{[1
]}

Jonck, Elizabeth ^{[2
]}

Joubert, Ernst J. ^{[2
]}

Plummer, Andrew R. ^{[1
]}

机构：

[1] Georgia State Univ, Dept Math & Stat, Atlanta, GA 30303 USA

[2] Univ Johannesburg, Dept Math, ZA-2006 Auckland Pk, South Africa

来源：

DISCRETE MATHEMATICS | 2007年 / 307卷 / 13期

关键词：

total restrained domination; trees;

D O I：

10.1016/j.disc.2006.09.014

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Let G = (V, E) be a graph. A set S subset of 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 gamma(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 gamma(tr)(T) >= [n+2/2]. Moreover, we show that if T is a tree of order n = 0 mod 4, then gamma(tr)(T)>=[n+2/2] + 1. We then constructively characterize the extremal trees T of order n achieving these lower bounds. (C) 2006 Elsevier B.V. All rights reserved.

引用

页码：1643 / 1650

页数：8