Alliances in graphs: Parameters, properties and applications—A survey

Abstract

In practice, an alliance can be a bond or connection between individuals, families, states, or entities, etc. Formally, a non-empty set of vertices of a graph is a defensive -alliance (resp. an offensive -alliance) if every vertex of (resp. the boundary of ) has at least more neighbors inside of than it has outside of . A powerful -alliance is both defensive -alliance and offensive -alliance. During the last decade there has been a remarkable development on these three kinds of alliances. Due to their variety of applications, the alliances in its broad sense have received a special attention from many scientists and researchers. There have been applications of alliances in several areas such as bioinformatics, distributed computing, web communities, social networks, data clustering, business, etc. Several -alliance numbers have been defined and a huge number of theoretical (algorithmic and computational) results are obtained for various graph classes. In this paper, we present a survey which covers a number of practical applications of alliances and the vast mathematical properties of the three types of -alliances by giving a special attention to the study of the associated -alliance (partition) numbers for different graph classes.

Keywords

• defensive (offensive powerful) -alliance
• boundary -alliance
• partitioning of graphs
• -alliance (partition) number
• graph class