2013/08/09 by Ismael G. Yero, Ismael González Yero, Yero, Ismael González +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Graph Labeling and Dimension Problems #math.CO
paper · pdf · doi:10.48550/arxiv.1308.2096
25 pages
arxiv created 2013/08/09 · openalex publication_date 2013/08/09 · arxiv updated 2013/08/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A set S of vertices of a graph G is a defensive k-alliance in G if every vertex of S has at least k more neighbors inside of S than outside. This is primarily an expository article surveying the principal known results on defensive alliances in graph. Its seven sections are: Introduction, Computational complexity and realizability, Defensive k-alliance number, Boundary defensive k-alliances, Defensive alliances in Cartesian product graphs, Partitioning a graph into defensive k-alliances, and Defensive k-alliance free sets.