On secure domination in trees

Abstract

A subset D of the vertex set of a graph G is a secure dominating set of G if D is a dominating set of G and if, for each vertex u not in D, there is a vertex v in D adjacent to u such that the swap set (D \ {v}) ∪ {u} is again a dominating set of G. The secure domination number of G, denoted by γs(G), is the cardinality of a smallest secure dominating set of G. In this paper, we prove that for any tree T on n ≥ 3 vertices, and the bounds are sharp, where ℓ and t are the numbers of leaves and stems of T , respectively. Moreover, we characterize the trees T such that .