- DISCRETE APPLIED MATHEMATICS Journal
- January 2009
Digital Object Identifier (DOI)
International Standard Serial Number (ISSN)
Electronic International Standard Serial Number (EISSN)
- 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.