Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
420949 | Discrete Applied Mathematics | 2007 | 7 Pages |
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 can be defended from an attack from outside of S, under an appropriate definition of what such a defense implies. Necessary and sufficient conditions for a set to be secure are determined.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Robert C. Brigham, Ronald D. Dutton, Stephen T. Hedetniemi,