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, 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) of G is the cardinality of a smallest secure set. Bounds on s(G) are presented. |
Year | DOI | Venue |
---|---|---|
2008 | 10.1016/j.dam.2007.08.037 | Discrete Applied Mathematics |
Keywords | Field | DocType |
security number,extremal graphs,smallest secure set,appropriate definition,entire set,subset x,defensive alliance,secure sets,defensive alliances | Graph,Discrete mathematics,Combinatorics,Vertex (geometry),Alliance,Cardinality,Mathematics | Journal |
Volume | Issue | ISSN |
156 | 5 | Discrete Applied Mathematics |
Citations | PageRank | References |
13 | 1.00 | 4 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Ronald D. Dutton | 1 | 190 | 27.80 |
Robert Lee | 2 | 13 | 1.00 |
Robert C. Brigham | 3 | 157 | 26.74 |