Offensive k-alliances in graphs

Abstract

Let $G=(V,E)$ be a simple graph. For a nonempty set $X\subset V,$ and a vertex $v\in V,$ ${\delta }_X(v)$ denotes the number of neighbors $v$ has in $X.$ A nonempty set $S\subset V$ is an \emph{offensive $r$-alliance} in $G$ if ${\delta }_S(v)\ge {\delta }_{\bar{S}}(v)+r,$ $\forall v\in \partial (S),$ where $\partial (S)$ denotes the boundary of $S$. An offensive $r$-alliance $S$ is called \emph{global} if it forms a dominating set. The \emph{global offensive $r$-alliance number} of $G$, denoted by ${\gamma }_r^o(G)$, is the minimum cardinality of a global offensive $r$-alliance in $G$. We show that the problem of finding optimal (global) offensive $r$-alliances is NP-complete and we obtain several tight bounds on ${\gamma }_r^o(G)$.

Cited by in corpus (1)

• On global offensive k-alliances in graphs