Premium
Characterizations of trees with equal domination parameters
Author(s) -
Hattingh Johannes H.,
Henning Michael A.
Publication year - 2000
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/1097-0118(200006)34:2<142::aid-jgt3>3.0.co;2-v
Subject(s) - dominating set , domination analysis , mathematics , combinatorics , vertex (graph theory) , constructive , graph , characterization (materials science) , cardinality (data modeling) , constructive proof , discrete mathematics , physics , computer science , process (computing) , optics , data mining , operating system
Let G = ( V , E ) be a graph. A set S ⊆ V is a restrained dominating set, if every vertex not in S is adjacent to a vertex in S and to a vertex in V − S . The restrained domination number of G , denoted by γ r ( G ), is the minimum cardinality of a restrained dominating set of G . A set S ⊆ V is a weak dominating set of G if, for every u in V − S , there exists a v ∈ S such that uv ∈ E and deg u ≥ deg v . The weak domination number of G , denoted by γ w ( G ), is the minimum cardinality of a weak dominating set of G . In this article, we provide a constructive characterization of those trees with equal independent domination and restrained domination numbers. A constructive characterization of those trees with equal independent domination and weak domination numbers is also obtained. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 142–153, 2000