Geodesic
Offensive alliances in graphs
Discussiones Mathematicae. Graph Theory, Tome 24 (2004) no. 2, pp. 263-275.

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: alliance, offensive, majority, graph 
@article{DMGT_2004_24_2_a8,
     author = {Favaron, Odile and Fricke, Gerd and Goddard, Wayne and Hedetniemi, Sandra and Hedetniemi, Stephen and Kristiansen, Petter and Laskar, Renu and Skaggs, R.},
     title = {Offensive alliances in graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {263--275},
     publisher = {mathdoc},
     volume = {24},
     number = {2},
     year = {2004},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2004_24_2_a8/}
}
TY  - JOUR
AU  - Favaron, Odile
AU  - Fricke, Gerd
AU  - Goddard, Wayne
AU  - Hedetniemi, Sandra
AU  - Hedetniemi, Stephen
AU  - Kristiansen, Petter
AU  - Laskar, Renu
AU  - Skaggs, R.
TI  - Offensive alliances in graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2004
SP  - 263
EP  - 275
VL  - 24
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2004_24_2_a8/
LA  - en
ID  - DMGT_2004_24_2_a8
ER  - 
%0 Journal Article
%A Favaron, Odile
%A Fricke, Gerd
%A Goddard, Wayne
%A Hedetniemi, Sandra
%A Hedetniemi, Stephen
%A Kristiansen, Petter
%A Laskar, Renu
%A Skaggs, R.
%T Offensive alliances in graphs
%J Discussiones Mathematicae. Graph Theory
%D 2004
%P 263-275
%V 24
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2004_24_2_a8/
%G en
%F DMGT_2004_24_2_a8
Favaron, Odile; Fricke, Gerd; Goddard, Wayne; Hedetniemi, Sandra; Hedetniemi, Stephen; Kristiansen, Petter; Laskar, Renu; Skaggs, R. Offensive alliances in graphs. Discussiones Mathematicae. Graph Theory, Tome 24 (2004) no. 2, pp. 263-275. http://geodesic.mathdoc.fr/item/DMGT_2004_24_2_a8/

[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.

[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.

[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.

[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.

[5] S.M. Hedetniemi, S.T Hedetniemi and P. Kristiansen, Alliances in graphs, J. Combin. Math. Combin. Comput., to appear.

[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.

[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.

[9] K.H. Shafique and R.D. Dutton, On satisfactory partitioning of graphs, Congress. Numer. 154 (2002) 183-194.

[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.