Geodesic
Offensive alliances in graphs
Discussiones Mathematicae. Graph Theory, Tome 24 (2004) no. 2, pp. 263-275

Voir la notice de l'article provenant de la source Library of Science

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 
@article{DMGT_2004_24_2_a8,
     author = {Favaron, Odile and Fricke, Gerd and Goddard, Wayne and Hedetniemi, Sandra and Hedetniemi, Stephen and Kristiansen, Petter and Laskar, Renu and Skaggs, R.},
     title = {Offensive alliances in graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {263--275},
     publisher = {mathdoc},
     volume = {24},
     number = {2},
     year = {2004},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2004_24_2_a8/}
}
TY  - JOUR
AU  - Favaron, Odile
AU  - Fricke, Gerd
AU  - Goddard, Wayne
AU  - Hedetniemi, Sandra
AU  - Hedetniemi, Stephen
AU  - Kristiansen, Petter
AU  - Laskar, Renu
AU  - Skaggs, R.
TI  - Offensive alliances in graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2004
SP  - 263
EP  - 275
VL  - 24
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2004_24_2_a8/
LA  - en
ID  - DMGT_2004_24_2_a8
ER  - 
%0 Journal Article
%A Favaron, Odile
%A Fricke, Gerd
%A Goddard, Wayne
%A Hedetniemi, Sandra
%A Hedetniemi, Stephen
%A Kristiansen, Petter
%A Laskar, Renu
%A Skaggs, R.
%T Offensive alliances in graphs
%J Discussiones Mathematicae. Graph Theory
%D 2004
%P 263-275
%V 24
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2004_24_2_a8/
%G en
%F DMGT_2004_24_2_a8
Favaron, Odile; Fricke, Gerd; Goddard, Wayne; Hedetniemi, Sandra; Hedetniemi, Stephen; Kristiansen, Petter; Laskar, Renu; Skaggs, R. Offensive alliances in graphs. Discussiones Mathematicae. Graph Theory, Tome 24 (2004) no. 2, pp. 263-275. http://geodesic.mathdoc.fr/item/DMGT_2004_24_2_a8/