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 n {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, n+2/3 γs(T) 2n+2ℓ-t/4 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 γs(T) = n+2/3.

Mathematics Subject Classication (2010): 05C69.

Key words: Tree, secure dominating set, secure domination number.