Loading...
Please wait, while we are loading the content...
Similar Documents
C O ] 2 0 M ar 2 00 7 Offensive k-alliances in graphs
| Content Provider | Semantic Scholar |
|---|---|
| Author | Fernau, Henning Rodŕıguez, J. A. Sigarreta, Jose Maria |
| Copyright Year | 2008 |
| Abstract | Let G = (V,E) be a simple graph. For a nonempty set X ⊂ V, and a vertex v ∈ V, δX(v) denotes the number of neighbors v has in X. A nonempty set S ⊂ V is an offensive r-alliance in G if δS(v) ≥ δS̄(v) + r, ∀v ∈ ∂(S), where ∂(S) denotes the boundary of S. An offensive r-alliance S is called global if it forms a dominating set. The global offensive r-alliance number of G, denoted by γ r (G), is the minimum cardinality of a global offensive r-alliance in G. We show that the problem of finding optimal (global) offensive r-alliances is NP-complete and we obtain several tight bounds on γ r (G). |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://arxiv.org/pdf/math/0703598v1.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
