Alliances in graphs: Parameters, properties and applications—A survey. Issue 2 (1st August 2018)

• Record Type: Journal Article
• Authors: Ouazine, Kahina; Slimani, Hachem; Tari, Abdelkamel
• Is Part Of: AKCE International Journal of Graphs and Combinatorics. Volume 15:Issue 2(2018)
• Page Start: 115
• Page End: 154
• Publication Date: 2018-08-01
• Subjects: Defensive (offensive powerful) k-alliance -- Boundary k-alliance -- Partitioning of graphs -- k-alliance (partition) number -- Graph class
• DOI: 10.1016/j.akcej.2017.05.002
• Languages: English
• ISSNs: 0972-8600

Abstract

Abstract: In practice, an alliance can be a bond or connection between individuals, families, states, or entities, etc. Formally, a non-empty set S of vertices of a graph G is a defensive k -alliance (resp. an offensive k -alliance) if every vertex of S (resp. the boundary of S ) has at least k more neighbors inside of S than it has outside of S . A powerful k -alliance is both defensive k -alliance and offensive ( k + 2 ) -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 k -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 k -alliances by giving a special attention to the study of the associated k -alliance (partition) numbers for different graph classes.