A note on the global offensive alliances in graphs

Nader Jafari Rad

---

URL :   http://research.shahed.ac.ir/WSR/WebPages/Report/PaperView.aspx?PaperID=85688
Date :  2018/12/11
Publish in :    Discrete Applied Mathematics
DOI :  https://doi.org/10.1016/j.dam.2018.04.019
Link :  http://dx.doi.org/https://doi.org/10.1016/j.dam.2018.04.019
Keywords :global offensive, alliance,graphs

Abstract :

---

A subset S of vertices in a graph G = (V, E) is a global offensive alliance if for every vertex v not in S, at least half of the vertices in the closed neighborhood of v are in S. The global offensive alliance number of G is the minimum cardinality among all global offensive alliances in G. A global offensive alliance D is called a global strong offensive alliance if for every vertex v not in S, more than half of the vertices in the closed neighborhood of v are in S. The global strong offensive alliance number of G is the minimum cardinality among all global strong offensive alliances in G. In this paper, we present new upper bounds for the global offensive alliance number as well as the global strong offensive alliance number of a graph. We improve previous upper bounds given in Harutyunyan (2014).