A lower bound for the distance k-domination number of trees

A subset D of vertices of a graph G = (V, E) is a distance k-dominating set for G if the distance between every vertex of V ? D and D is at most k. The minimum size of a distance k-dominating set of G is called the distance k-domination number γ_k(G) of G. In this paper we prove that (2k + 1)γ_k(T) ≥ ¦V¦ + 2k ? kn₁ for each tree T = (V, E) with n₁ leafs, and we characterize the class of trees that satisfy the equality (2k + 1)γ_k(T) = ¦V¦ + 2k ? kn₁. Our results generalize those of Lemanska [4] for k = 1 and of Cyman, Lemanska and Raczek [1] for k = 2.