Rooted Secure Sets of Trees
Yiu Yu Ho, Ronald D. Dutton, Teresa W. Haynes · AKCE International Journal of Graphs and Combinatorics · 2009
Let G =( V,E) be a graph. A set S ⊆ V is a defensive alliance if for all x ∈ S, |N[x] ∩ S |≥| N[x] − S|. Thus, each vertex of a defensive alliance can, with the aid of its neighbors in S, be defended from attacks by its neighbors outside of S. As etS is a secure set if every subset X ⊆ S can be defended from attacks by vertices outside of S, under an appropriate definition of such attacks and defenses. Given G and x ∈ V, a secure set rooted at x is a secure set that contains x. Polynomial algorithms for computing the cardinality of a minimum rooted secure set of trees are presented.