期刊名称：AKCE International Journal of Graphs and Combinatorics
印刷版ISSN：0972-8600
出版年度：2018
卷号：15
期号：2
页码：115-154
DOI：10.1016/j.akcej.2017.05.002
语种：English
出版社：Elsevier
摘要：AbstractIn practice, an alliance can be a bond or connection between individuals, families, states, or entities, etc. Formally, a non-empty setSof vertices of a graphGis a defensivek-alliance (resp. an offensivek-alliance) if every vertex ofS(resp. the boundary ofS) has at leastkmore neighbors inside ofSthan it has outside ofS. A powerfulk-alliance is both defensivek-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. Severalk-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 ofk-alliances by giving a special attention to the study of the associatedk-alliance (partition) numbers for different graph classes.
关键词：KeywordsDefensive (offensive powerful)k-allianceBoundaryk-alliancePartitioning of graphsk-alliance (partition) numberGraph class
