Global defensive alliances in graphs (Q1422134)

Summary: A defensive alliance in a graph \(G = (V,E)\) is a set of vertices \(S \subseteq V\) satisfying the condition that for every vertex \(v\in 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 study global defensive alliances in graphs.