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.
相似文献