Alliances in Graphs

Petter Kristiansen1, Sandra M.Hedetniemi2, Stephen T.Hedetniemi3
1Department of Informatics University of Bergen N-5020 Bergen, Norway
2 Department of Computer Science Clemson University Clemson, SC 29634, USA
3Department of Computer Science Clemson University Clemson, SC 29634, USA

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.