Further results on weak domination in graphs

Abstract

Let G = (V, E) be a graph. A set S ⊆ V is a weak dominating set of G if for every u ∈ 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. We show that if T ≠ K₂ is a tree of order n, then γ_w(T) ≥ [(n + 2)/3]. We Constructively characterize the extremal trees T of order n achieving this lower bound. Furthermore, we show that if G is a connected graph of order n ≥ 3 which is not a star, then γ_w(G) ≤ n - 2 and characterize those connected graphs of order n achieving n - 2.