On the complement graph and defensive \(k\)-alliances

DOI10.1016/j.dam.2008.12.006zbMath1211.05125OpenAlexW2159335783MaRDI QIDQ1026126

Henning Fernau, Sergio Bermudo, José María Sigarreta-Almira

Publication date: 24 June 2009

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2008.12.006

zbMATH Keywords

NP-completenessindependent setdomination numbercomplement graphdefensive alliances

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

On structural parameterizations of the offensive alliance problem ⋮ Globally minimal defensive alliances ⋮ Parameterized intractability of defensive alliance problem ⋮ Structural parameterization of alliance problems ⋮ Partitioning a graph into offensive \(k\)-alliances ⋮ Alliances in graphs: parameters, properties and applications -- a survey ⋮ Partitioning a graph into defensive \(k\)-alliances ⋮ Aspects of upper defensive alliances ⋮ Alliances in graphs of bounded clique-width ⋮ Alliances and Related Domination Parameters ⋮ Defensive alliances in graphs ⋮ Unnamed Item ⋮ Offensive alliances in graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Global defensive \(k\)-alliances in graphs
• Defensive \(k\)-alliances in graphs
• Global defensive alliances in graphs
• Small Alliances in Graphs
• On Hadwiger's Number and the Stability Number
• Spectral study of alliances in graphs