A linear algorithm for secure domination in trees

A subset XX of the vertex set of a graph GG is a secure dominating set   of GG if XX is a dominating set of GG and if, for each vertex uu not in XX, there is a neighbouring vertex vv of uu in XX such that the swap set (X−{v})∪{u}(X−{v})∪{u} is again a dominating set of GG. The secure domination number   of GG, denoted by γs(G)γs(G), is the cardinality of a smallest secure dominating set of GG. A linear algorithm is proposed in this paper for finding a minimum secure dominating set and hence the value γs(T)γs(T) for a tree TT. The algorithm is based on a strategy of repeatedly pruning away pendent spiders of TT after having dominated them securely.