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 (2004)

  • Volume: 24, Issue: 2, page 263-275
  • ISSN: 2083-5892

Abstract

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

How to cite

top

Odile Favaron, et al. "Offensive alliances in graphs." Discussiones Mathematicae Graph Theory 24.2 (2004): 263-275. <http://eudml.org/doc/270644>.

@article{OdileFavaron2004,
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.},
author = {Odile Favaron, Gerd Fricke, Wayne Goddard, Sandra M. Hedetniemi, Stephen T. Hedetniemi, Petter Kristiansen, Renu C. Laskar, R. Duane Skaggs},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {alliance; offensive; majority; graph},
language = {eng},
number = {2},
pages = {263-275},
title = {Offensive alliances in graphs},
url = {http://eudml.org/doc/270644},
volume = {24},
year = {2004},
}

TY - JOUR
AU - Odile Favaron
AU - Gerd Fricke
AU - Wayne Goddard
AU - Sandra M. Hedetniemi
AU - Stephen T. Hedetniemi
AU - Petter Kristiansen
AU - Renu C. Laskar
AU - R. Duane Skaggs
TI - Offensive alliances in graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2004
VL - 24
IS - 2
SP - 263
EP - 275
AB - 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.
LA - eng
KW - alliance; offensive; majority; graph
UR - http://eudml.org/doc/270644
ER -

References

top
  1. [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. Zbl0717.05065
  2. [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. Zbl0842.05051
  3. [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. Zbl0933.05117
  4. [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. Zbl0965.90053
  5. [5] S.M. Hedetniemi, S.T Hedetniemi and P. Kristiansen, Alliances in graphs, J. Combin. Math. Combin. Comput., to appear. Zbl1051.05068
  6. [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. [7] M. Luby, A simple parallel algorithm for the maximal independent set problem, SIAM J. Comput. 15 (1986) 1036-1053, doi: 10.1137/0215074. Zbl0619.68058
  8. [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. Zbl0997.68088
  9. [9] K.H. Shafique and R.D. Dutton, On satisfactory partitioning of graphs, Congress. Numer. 154 (2002) 183-194. Zbl1022.05068
  10. [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. Zbl0723.05058

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.