Defensive k-alliances in graphs

Rodriguez-Velazquez, J. A.; Yero, I. G.; Sigarreta, J. M.

Defensive k-alliances in graphs

Authors

Rodriguez-Velazquez, J. A.

Yero, I. G.

Sigarreta, J. M.

Description

Let $Γ=(V,E)$ be a simple graph. For a nonempty set $X\subseteq V$, and a vertex $v\in V$, $δ_{X}(v)$ denotes the number of neighbors $v$ has in $X$. A nonempty set $S\subseteq V$ is a \emph{defensive $k$-alliance} in $Γ=(V,E)$ if $δ_S(v)\ge δ_{\bar{S}}(v)+k,$ $\forall v\in S.$ The defensive $k$-alliance number of $Γ$, denoted by $a_k(Γ)$, is defined as the minimum cardinality of a defensive $k$-alliance in $Γ$. We study the mathematical properties of $a_k(Γ)$.