On a graph’s security number

Abstract

A secure set $S\subseteq V$ of graph $G=(V,E)$ is a set whose every nonempty subset can be successfully defended from an attack, under appropriate definitions of “attack” and “defended.” The set $S$ is secure when $|N\left[X\right]\cap S|\ge |N\left[X\right]-S|$ for every $X\subseteq S$. The smallest cardinality of a secure set in $G$ is the security number of $G$. New bounds for the security number are established, the effect of some graph modifications on the security number is investigated, and the exact value of the security number for some families of graphs is given.