A survey on alliances in graphs: Defensive alliances

Abstract

A set S of vertices of a graph G is a defensive fc-alliance in G, if every vertex of S has at least k more neighbors inside than outside of S. This is primarily an expository article surveying the principal known results on defensive alliances in graphs. It contains the following seven sections: Introduction, Computational complexity and realizability, Defensive fc-alliance number, Boundary defensive k-alliances, Defensive alliances in Cartesian product graphs, Partitioning a graph into defensive fc-alliances, and Defensive fc-alliance free sets. © 2017 Utilitas Mathematica Publishing Inc.. All rights reserved.