A Tight Bound on the Cardinalities of Maximum Alliance-Free and Minimum Alliance-Cover Sets

Abstract

A defensive $k$-alliance in a graph $G=(V,E)$ is a set of vertices $A\subseteq V$ such that for every vertex $v\in A$, the number of neighbors $v$ has in $A$ is at least $k$ more than the number of neighbors it has in $V–A$ (where $k$ is a measure of the strength of the alliance). In this paper, we deal with two types of sets associated with defensive $k$-alliances: maximum defensive $k$-alliance free and minimum defensive $k$-alliance cover sets.

Define a set $X\subseteq V$ to be maximum defensive $k$-alliance free if $X$ does not contain any defensive $k$-alliance and is the largest such set. A set $Y\subseteq V$ is called a \emph{minimum defensive $k$-alliance cover} if $Y$ contains at least one vertex from each defensive $k$-alliance and is a set of minimum cardinality satisfying this property. We present bounds on the cardinalities of maximum defensive $k$-alliance free and minimum defensive $k$-alliance cover sets.