Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
419799 | Discrete Applied Mathematics | 2009 | 6 Pages |
Abstract
Let G=(V,E)G=(V,E) be a simple graph. For a nonempty set X⊂VX⊂V, and a vertex v∈V,δX(v)v∈V,δX(v) denotes the number of neighbors vv has in XX. A nonempty set S⊂VS⊂V is an offensive rr-alliance in GG if δS(v)≥δS̄(v)+r,∀v∈∂(S), where ∂(S)∂(S) denotes the boundary of SS. An offensive rr-alliance SS is called global if it forms a dominating set. The global offensive rr-alliance number of GG, denoted by γro(G), is the minimum cardinality of a global offensive rr-alliance in GG. We show that the problem of finding optimal (global) offensive rr-alliances is NP-complete and we obtain several tight bounds on γro(G).
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Henning Fernau, Juan A. Rodríguez, José M. Sigarreta,