Alliance free and alliance cover sets (Q2430310)

A defensive (offensive) \(k\)-alliance in \(\Gamma = (V,E)\) is a set \(S \subseteq V\) such that every \(v\) in \(S\) (in the boundary of \(S\)) has at least \(k\) more neighbors in \(S\) than it has in \(V \setminus S\). A set \(X \subseteq V\) is defensive (offensive) \(k\)-alliance free, if for all defensive (offensive) \(k\)-alliance \(S\), \(S \setminus X \neq \phi\), i.e., \(X\) does not contain any defensive (offensive) \(k\)-alliance as a subset. A set \(Y \subseteq V\) is a defensive (offensive) \(k\)-alliance cover, if for all defensive (offensive) \(k\)-alliance \(S\), \(S \cap Y \neq \phi\), i.e., \(Y\) contains at least one vertex from each defensive (offensive) \(k\)-alliance of \(\Gamma\). In this paper, the authors prove several mathematical properties of defensive (offensive) \(k\)-alliance free sets and defensive (offensive) \(k\)-alliance cover sets, including tight bounds on their cardinality.