PDF
Discussiones Mathematicae Graph Theory 24(2) (2004) 263-275
DOI: https://doi.org/10.7151/dmgt.1230
OFFENSIVE ALLIANCES IN GRAPHS
Odile Favaron1, Gerd Fricke2, Wayne Goddard3,4, Sandra M. Hedetniemi4, Stephen T. Hedetniemi4, Petter Kristiansen5, Renu C. Laskar4 and R. Duane Skaggs2
1Université Paris-Sud, 2Morehead State University, 3University of KwaZulu-Natal, Durban, 4Clemson University and 5University of Bergen
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.Keywords: alliance, offensive, majority, graph.
2000 Mathematics Subject Classification: 05C90, 05C69.
References
| [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. |
Received 20 May 2002
Revised 1 October 2003
Close