Upper bounds on the global offensive alliances in graphs

Nader Jafari Rad

---

URL :   http://research.shahed.ac.ir/WSR/WebPages/Report/PaperView.aspx?PaperID=158316
Date :  2021/01/31
Publish in :    Discrete Applied Mathematics
DOI :  https://doi.org/https://doi.org/10.1016/j.dam.2020.10.010
Link :  http://dx.doi.org/https://doi.org/10.1016/j.dam.2020.10.010
Keywords :Global offensive alliances Global strong offensive alliances Probabilistic methods

Abstract :

---

A subset of vertices in a graph is called a global offensive alliance if for every vertex not in , at least half of the vertices in the closed neighborhood of are in . A global offensive alliance is called a global strong offensive alliance if for every vertex not in , more than half of the vertices in the closed neighborhood of are in . The global offensive alliance number (global strong offensive alliance number, respectively) of is the minimum cardinality of a global offensive alliance (global strong offensive alliance, respectively) in . In this paper, we present new (probabilistic) upper bounds for the global offensive alliance number as well as the global strong offensive alliance number of a graph, improving previous bounds given in Harutyunyan (2014).