Title

Bounds On A Graph'S Security Number

Keywords

Defensive alliances; Extremal graphs; Secure sets

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.

Publication Date

3-1-2008

Publication Title

Discrete Applied Mathematics

Volume

156

Issue

5

Number of Pages

695-704

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.1016/j.dam.2007.08.037

Socpus ID

39049142462 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/39049142462

This document is currently not available here.

Share

COinS