Download PDF - Offensive alliances in graphsAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

Offensive alliances in graphs

Authors 1, 2, 3, 4, 4, 4,

Affiliations

  1. Université Paris-Sud
  2. Morehead State University
  3. University of KwaZulu-Natal, Durban
  4. Clemson University
  5. University 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

ENG
alliance, offensive, majority, graph

Bibliography

  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.
Discussiones Mathematicae Graph Theory
2004/24/2
Export to PBN, Opens in new tab
Pages:
263-275
Main language of publication
English
Received
2002-05-20
Accepted
2003-10-01
Published
2004

DOI: 10.7151/dmgt.1230

Exact and natural sciences