Offensive alliances in graphs

• Autorzy: Odile Favaron , Gerd Fricke , Wayne Goddard , Sandra M. Hedetniemi , Stephen T. Hedetniemi , Petter Kristiansen , Renu C. Laskar , R. Duane Skaggs
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

alliance; offensive; majority; graph

Kategorie tematyczne

• 05C90: Applications
• 05C69: Dominating sets, independent sets, cliques

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2004
• Tom: 24
• Numer: 2
• Strony: 263-275

Daty

wydano

2004

otrzymano

2002-05-20

poprawiono

2003-10-01

Twórcy

autor

Odile Favaron

• Université Paris-Sud

autor

Gerd Fricke

• Morehead State University

autor

Wayne Goddard

• University of KwaZulu-Natal, Durban
• Clemson University

autor

Sandra M. Hedetniemi

• Clemson University

autor

Stephen T. Hedetniemi

• Clemson University

autor

Petter Kristiansen

• University of Bergen

autor

Renu C. Laskar

• Clemson University

autor

R. Duane Skaggs

• Morehead State University

Bibliografia

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

Identyfikatory

DOI

10.7151/dmgt.1230