Security in graphs

Abstract

Alliances are associations which are created for the mutual benefit of the parties involved. These can take the form of formal agreements between nations to cooperate for some purpose, or, in general, collaboration contracts agreed between “communities” (of any type, such as people, businesses, computers, web-pages, molecules, species, etc.) operating in the same environment. Such alliances can be studied mathematically by reducing each alliance to a graph-theoretical problem, where objects are represented by vertices while edges represent the corresponding relationship between objects. The study of alliances in graphs was initiated by Kristiansen et al. (2004). One particular type of alliance is called a “defensive alliance”. For any subset S of vertices of a graph G, a defensive alliance is one whereby, for any x ∈ S, there are at least as many defenders (that is, vertices in the closed neighbourhood of x which are in S) as there are attackers (that is, vertices in the neighbourhood of x which are not in S). In such an instance, any attack on a single vertex in a defensive alliance can be thwarted. However, in more authentic settings, alliances are created so that an attack on any subset of the alliance can be defended, and not only an attack on a single member of the alliance. This generalisation of defensive alliances was introduced by Brigham et al. (2007) through the definition of the concept of “secure sets”. Loosely speaking, a set S of vertices of a graph G is secure if any subset X ⊆ S can be defended from an attack from outside S, under an appropriate definition of what such a defense implies. The security number s(G) of G is the size of a smallest secure set. In this project we find, collate, review and analyse the main results on secure sets dispersed in literature.