Article ID Journal Published Year Pages File Type
420652 Discrete Applied Mathematics 2008 10 Pages PDF
Abstract

Let G=(V,E)G=(V,E) be a graph. A set S⊆VS⊆V is a defensive alliance if |N[x]∩S|⩾|N[x]-S||N[x]∩S|⩾|N[x]-S| for every x∈Sx∈S. Thus, each vertex of a defensive alliance can, with the aid of its neighbors in S, be defended from attack by its neighbors outside of S. An entire set S   is secure if any subset X⊆SX⊆S, not just singletons, can be defended from an attack from outside of S  , under an appropriate definition of what such a defense implies. The security number s(G)s(G) of G   is the cardinality of a smallest secure set. Bounds on s(G)s(G) are presented.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , ,