Minimum-cardinality global defensive alliances in general graphs

André Rossi () and Alok Singh ()
Additional contact information
André Rossi: Université Paris Dauphine - PSL
Alok Singh: University of Hyderabad

Annals of Operations Research, 2025, vol. 349, issue 3, No 14, 1931 pages

Abstract: Abstract A subset S of vertices of an undirected graph G is a defensive alliance if at least half of the vertices in the closed neighborhood of each vertex of S are in S. A defensive alliance is a global defensive alliance if it is also a dominating set of G. This paper addresses the problem of finding minimum-cardinality global defensive alliances for general graphs. Two integer linear programming formulations are proposed to address this problem, the second one being an improved version of the first one in which the constraints are attempted for tightening with a cubing-time algorithm. Two new lower bounds on the cardinality of a defensive global alliance are proposed: the first one is based on a linear time algorithm and is shown to be tighter than three of the four lower bounds from the literature, and the second one is derived from the linear programming relaxation of the aforementioned integer linear programming formulations of the problem. An upper bound on the global defensive alliance number is obtained using a greedy peeling algorithm that is shown to be at least as good as an upper bound of the literature, however it is also shown that the proposed algorithm may be unable to find an optimal solution for some graphs. Finally, numerical experiments are carried out on the 78 DIMACS instances and on 75 Erdős-Rényi graphs with up to 10,000 vertices in order to show the effectiveness of the proposed approaches.

Keywords: Global defensive alliances; Dominating set; Graphs; Integer linear programming (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10479-025-06571-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:349:y:2025:i:3:d:10.1007_s10479-025-06571-2

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-025-06571-2

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().