Trees with Equal Domination and Restrained Domination Numbers |
| |
Authors: | Peter Dankelmann Johannes H Hattingh Michael A Henning Henda C Swart |
| |
Institution: | (1) School of Mathematical Sciences, University of KwaZulu-Natal, Durban, 4041, South Africa;(2) Department of Mathematics and Statistics, Georgia State University, Atlanta, Georgia 30303-3083, USA;(3) School of Mathematical Sciences, University of KwaZulu-Natal, Pietermaritzburg, 3209, South Africa |
| |
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 S 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. |
| |
Keywords: | domination domination excellent trees restrained domination |
本文献已被 SpringerLink 等数据库收录! |
|