Alliances versus cover and alliance free sets
J.A. Rodrı́guez, José M. Sigarreta · arXiv (Cornell University) · 2006
A \emph{defensive} (\emph{offensive}) $k$-\emph{alliance} in $\Gamma=(V,E)$ is a set $S\subseteq V$ such that for every $v\in S$ ($v\in \partial S$), the number of neighbors $v$ has in $S$ is at least $k$ more than the number of neighbors it has in $V\setminus S$. A set $X\subseteq V$ is \emph{defensive} (\emph{offensive}) $k$-\emph{alliance free,} if for all defensive (offensive) $k$-alliance $S$, $S\setminus X eq\emptyset$, i.e., $X$ do not contain any defensive (offensive) $k$-alliance as a subset. A set $Y \subseteq V$ is a \emph{defensive} (\emph{offensive}) $k$-\emph{alliance cover}, if for all defensive (offensive) $k$-alliance $S$, $S\cap Y eq\emptyset$, i.e., $Y$ contains at least one vertex from each defensive (offensive) $k$-alliance of $\Gamma$. In this paper we obtain several mathematical properties of defensive (offensive) $k$-alliances, $k$-alliance free sets and $k$-alliance cover sets, and we explore some of their interrelations.