Alliances in Graphs

Abstract

A defensive alliance in a graph $G=(V,E)$ is a set of vertices $S\subseteq V$ satisfying the condition that every vertex $v\in S$ has at most one more neighbor in $V–S$ than it has in $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$. In this paper, we introduce this new concept, together with a variety of other kinds of alliances, and initiate the study of their mathematical properties.