Offensive Alliances in Graphs
Odile Favaron, Gerd H. Fricke, Wayne Goddard, Sandra M. Hedetniemi, Stephen T. Hedetniemi, Petter Kristiansen, Renu C. Laskar, Duane Skaggs · 2022
A set S is an offensive alliance if for every vertex v in its boundary N(S) − S it holds that the majority of vertices in u’s closed neighbourhood are in S . The offensive alliance number is the minimum cardinality of an offensive alliance. In this paper we explore the bounds on the offensive alliance and the strong offensive alliance numbers (where a strict majority is required). In particular, we show that the offensive alliance number is at most 2/3 the order and the strong offensive alliance number at most 5/6 the order.