On the Global Offensive Alliance Number of a Graph Articles uri icon

authors

  • SIGARRETA ALMIRA, JOSE MARIA
  • RODRIGUEZ, J.A.

publication date

  • January 2009

start page

  • 219

end page

  • 226

issue

  • 2

volume

  • 157

International Standard Serial Number (ISSN)

  • 0166-218X

Electronic International Standard Serial Number (EISSN)

  • 1872-6771

abstract

  • An offensive alliance in a graph Gamma=(V,E) is a set of vertices S⊂V where for each vertex v in its boundary the majority of vertices in v's closed neighborhood are in S. In the case of strong offensive alliance, strict majority is required. An alliance S is called global if it affects every vertex in V∖S, that is, S is a dominating set of Gamma. The global offensive alliance numbergammao(Gamma) is the minimum cardinality of a global offensive alliance in Gamma. An offensive alliance is connected if its induced subgraph is connected. The global-connected offensive alliance number, gammaco(Gamma), is the minimum cardinality of a global-connected offensive alliance in Gamma. In this paper we obtain several tight bounds on gammao(Gamma) and gammaco(Gamma) in terms of several parameters of Gamma. The case of strong alliances is studied by analogy.