Title
Security In Graphs
Keywords
Alliances; Defensive alliances
Abstract
Let G = (V, E) be a graph. A set S ⊆ V is a defensive alliance if | N [x] ∩ S | ≥ | N [x] - S | for every x ∈ 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 ⊆ 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.
Publication Date
8-15-2007
Publication Title
Discrete Applied Mathematics
Volume
155
Issue
13
Number of Pages
1708-1714
Document Type
Article
Personal Identifier
scopus
DOI Link
https://doi.org/10.1016/j.dam.2007.03.009
Copyright Status
Unknown
Socpus ID
34547433680 (Scopus)
Source API URL
https://api.elsevier.com/content/abstract/scopus_id/34547433680
STARS Citation
Brigham, Robert C.; Dutton, Ronald D.; and Hedetniemi, Stephen T., "Security In Graphs" (2007). Scopus Export 2000s. 6429.
https://stars.library.ucf.edu/scopus2000/6429