Global Defensive Alliances
Teresa W. Haynes, Stephen T. Hedetniemi, Michael A. Henning · 2022
A defensive alliance in a graph G = ( V, E ) is a set of vertices S ⊆ V satisfying the condition that for every vertex v ∈ S , the number of neighbors v has in S plus one (counting v ) is at least as large as the number of neighbors it has in V — S . Because of such an alliance, the vertices in S , agreeing to mutually support each other, have the strength of numbers to be able to defend themselves from the vertices in V — S. A defensive alliance S is called global if it effects every vertex in V — S, that is, every vertex in V — S is adjacent to at least one member of the alliance S. Note that a global defensive alliance is a dominating set. We summarize results and list some open problems on global defensive alliances in graphs.