# Offensive alliances in graphs

Odile Favaron; Gerd Fricke; Wayne Goddard; Sandra M. Hedetniemi; Stephen T. Hedetniemi; Petter Kristiansen; Renu C. Laskar; R. Duane Skaggs

Discussiones Mathematicae Graph Theory (2004)

- Volume: 24, Issue: 2, page 263-275
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topOdile Favaron, et al. "Offensive alliances in graphs." Discussiones Mathematicae Graph Theory 24.2 (2004): 263-275. <http://eudml.org/doc/270644>.

@article{OdileFavaron2004,

abstract = {A set S is an offensive alliance if for every vertex v in its boundary N(S)- S it holds that the majority of vertices in v's closed neighbourhood are in S. The offensive alliance number is the minimum cardinality of an offensive alliance. In this paper we explore the bounds on the offensive alliance and the strong offensive alliance numbers (where a strict majority is required). In particular, we show that the offensive alliance number is at most 2/3 the order and the strong offensive alliance number is at most 5/6 the order.},

author = {Odile Favaron, Gerd Fricke, Wayne Goddard, Sandra M. Hedetniemi, Stephen T. Hedetniemi, Petter Kristiansen, Renu C. Laskar, R. Duane Skaggs},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {alliance; offensive; majority; graph},

language = {eng},

number = {2},

pages = {263-275},

title = {Offensive alliances in graphs},

url = {http://eudml.org/doc/270644},

volume = {24},

year = {2004},

}

TY - JOUR

AU - Odile Favaron

AU - Gerd Fricke

AU - Wayne Goddard

AU - Sandra M. Hedetniemi

AU - Stephen T. Hedetniemi

AU - Petter Kristiansen

AU - Renu C. Laskar

AU - R. Duane Skaggs

TI - Offensive alliances in graphs

JO - Discussiones Mathematicae Graph Theory

PY - 2004

VL - 24

IS - 2

SP - 263

EP - 275

AB - A set S is an offensive alliance if for every vertex v in its boundary N(S)- S it holds that the majority of vertices in v's closed neighbourhood are in S. The offensive alliance number is the minimum cardinality of an offensive alliance. In this paper we explore the bounds on the offensive alliance and the strong offensive alliance numbers (where a strict majority is required). In particular, we show that the offensive alliance number is at most 2/3 the order and the strong offensive alliance number is at most 5/6 the order.

LA - eng

KW - alliance; offensive; majority; graph

UR - http://eudml.org/doc/270644

ER -

## References

top- [1] R. Aharoni, E.C. Milner and K. Prikry, Unfriendly partitions of graphs, J. Combin. Theory (B) 50 (1990) 1-10, doi: 10.1016/0095-8956(90)90092-E. Zbl0717.05065
- [2] J.E. Dunbar, S.T. Hedetniemi, M.A. Henning and P.J. Slater, Signed domination in graphs, in: ``Graph Theory, Combinatorics and Algorithms'' Y. Alavi and A. Schwenk, eds. (Wiley, 1995) 311-321. Zbl0842.05051
- [3] Z. Füredi and D. Mubayi, Signed domination in regular graphs and set-systems, J. Combin. Theory (B) 76 (1999) 223-239, doi: 10.1006/jctb.1999.1905. Zbl0933.05117
- [4] M.U. Gerber and D. Kobler, Partitioning a graph to satisfy all vertices, European J. Oper. Res. 125 (2000) 283-291, doi: 10.1016/S0377-2217(99)00459-2. Zbl0965.90053
- [5] S.M. Hedetniemi, S.T Hedetniemi and P. Kristiansen, Alliances in graphs, J. Combin. Math. Combin. Comput., to appear. Zbl1051.05068
- [6] N. Linial, D. Peleg, Y. Rabinovitch and M. Saks, Sphere packings and local majorities in graphs, In 2nd ISTCS, 141-149. IEEE Computer Soc. Press, June 1993.
- [7] M. Luby, A simple parallel algorithm for the maximal independent set problem, SIAM J. Comput. 15 (1986) 1036-1053, doi: 10.1137/0215074. Zbl0619.68058
- [8] D. Peleg, Local majorities, coalitions and monopolies in graphs: a review, Theoret. Comput. Sci. 282 (2002) 231-257, doi: 10.1016/S0304-3975(01)00055-X. Zbl0997.68088
- [9] K.H. Shafique and R.D. Dutton, On satisfactory partitioning of graphs, Congress. Numer. 154 (2002) 183-194. Zbl1022.05068
- [10] S. Shelah and E.C. Milner, Graphs with no unfriendly partitions, in: A Tribute to Paul Erdős, A. Baker et al. eds. (Cambridge University Press, 1990) 373-384. Zbl0723.05058

## Citations in EuDML Documents

top## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.