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, Tome 24 (2004), p. 263-275 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

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.

Publié le : 2004-01-01
EUDML-ID : urn:eudml:doc:270644 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1230,
     author = {Odile Favaron and Gerd Fricke and Wayne Goddard and Sandra M. Hedetniemi and Stephen T. Hedetniemi and Petter Kristiansen and Renu C. Laskar and R. Duane Skaggs},
     title = {Offensive alliances in graphs},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {24},
     year = {2004},
     pages = {263-275},
     zbl = {1064.05112},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1230}
}

Odile Favaron; Gerd Fricke; Wayne Goddard; Sandra M. Hedetniemi; Stephen T. Hedetniemi; Petter Kristiansen; Renu C. Laskar; R. Duane Skaggs. Offensive alliances in graphs. Discussiones Mathematicae Graph Theory, Tome 24 (2004) pp. 263-275. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1230/

[000] [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. | Zbl 0717.05065

[001] [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. | Zbl 0842.05051

[002] [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. | Zbl 0933.05117

[003] [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. | Zbl 0965.90053

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

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

[006] [7] M. Luby, A simple parallel algorithm for the maximal independent set problem, SIAM J. Comput. 15 (1986) 1036-1053, doi: 10.1137/0215074. | Zbl 0619.68058

[007] [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. | Zbl 0997.68088

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

[009] [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. | Zbl 0723.05058