$k$-STRONG DEFENSIVE ALLIANCES IN GRAPHS

Abstract

In a simple connected graph $G=(V,E)$, a subset $S$ of $V$ is a defensive alliance if every vertex $v\in S$ has at most one more neighbour in $V-S$ than it has in $S$. The minimum cardinality of a defensive alliance in $G$ is called the defensive alliance number of $G$, denoted by $a(G)$. A $k$-strong defensive alliance $S$ is a defensive alliance in $G$, in which removal of any set of at most $k$ vertices does not affect its defensive property. The $k$-strong defensive alliance number of $G$ is the minimum cardinality of a $k$-strong defensive alliance in $G$, denoted by $a^{k}(G)$. In this paper, some properties of $k$-strong defensive alliances are discussed and the $k$-strong defensive alliance numbers of some classes of graphs are obtained.