Maximum Alliance-Free and Minimum Alliance-Cover Sets
Khurram Shafique, Ronald D. Dutton · 2022
A defensive k—alliance in a graph G = (V, E) is a set of vertices A ⊆ V such that for every vertex v ∈ A, the number of neighbors v has in A is at least as large as the number of neighbors it has in V−S plus k (where k is the strength of k :–alliance). An offensive k–alliance is a set of vertices A ⊆ V such that for every vertex v ∈ ∂ dA, the number of neighbors v has in A is at least as large as the number of neighbors it has in V − S plus k. In this paper, we deal with two types of sets associated with these k –alliances that we refer to as maximum k –alliance free and minimum k –alliance cover sets respectively. We define a set X ⊆ V to be maximum k–alliance free (for some type of k –alliance) if X does not contain any k –alliance (of that type) and X is a set of largest cardinality among all such sets. A set Y ⊆ V is called minimum k –alliance cover (for some type of k –alliance) if Y contains at least one vertex from each k –alliance (of that type) and is a set of minimum cardinality satisfying this property. We present bounds on the cardinality of maximum k –alliance free and minimum alliance k –cover sets and explore their inter-relation. The existence of forbidden subgraphs for graphs induced by these sets is also questioned.