Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
420712 | Discrete Applied Mathematics | 2009 | 8 Pages |
An offensive alliance in a graph Γ=(V,E)Γ=(V,E) is a set of vertices S⊂VS⊂V where for each vertex vv in its boundary the majority of vertices in vv’s closed neighborhood are in SS. In the case of strong offensive alliance, strict majority is required. An alliance SS is called global if it affects every vertex in V∖SV∖S, that is, SS is a dominating set of ΓΓ. The global offensive alliance number γo(Γ)γo(Γ) is the minimum cardinality of a global offensive alliance in ΓΓ. An offensive alliance is connected if its induced subgraph is connected. The global-connected offensive alliance number , γco(Γ)γco(Γ), is the minimum cardinality of a global-connected offensive alliance in ΓΓ.In this paper we obtain several tight bounds on γo(Γ)γo(Γ) and γco(Γ)γco(Γ) in terms of several parameters of ΓΓ. The case of strong alliances is studied by analogy.