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.