On computing secure domination of trees.

Let G = (V , E) be a graph. A subset D ⊆ V is a dominating set of G if for each v ∈ V ∖ D there is a vertex u ∈ D adjacent to v. A dominating set D of G is a secure dominating set of G if for each v ∈ V ∖ D there is a vertex u ∈ D adjacent to v such that (D ∖ { u }) ∪ { v } is also a dominating set of G. The minimum cardinality of a secure dominating set of G is called the secure domination number of G. Burger et al. [A linear algorithm for secure domination in trees, Discrete Appl. Math. 171 (2014) 15–27] proposed a nontrivial algorithm for computing a minimum secure dominating set of a given tree in linear time and space. In this paper, we give a dynamic programming algorithm to compute the secure domination number of a given tree T = (V , E) in (| V |) time and space and then using a backtracking search algorithm we can find a minimum secure dominating set of T in (| V |) time and space that its implementation is much simpler than the implementation of the algorithm proposed by Burger et al. [ABSTRACT FROM AUTHOR]