Bounds on a graph's security number

Abstract

Let $G=(V,E)$ be a graph. A set $S\subseteq V$ is a defensive alliance if $|N[x]\cap S|⩾|N[x]-S|$ for every $x\in 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\subseteq 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.