Geodesic
Bounds on the global offensive k-alliance number in graphs
Discussiones Mathematicae. Graph Theory, Tome 29 (2009) no. 3, pp. 597-613.

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

Let G = (V(G),E(G)) be a graph, and let k ≥ 1 be an integer. A set S ⊆ V(G) is called a global offensive k-alliance if |N(v)∩S| ≥ |N(v)-S|+k for every v ∈ V(G)-S, where N(v) is the neighborhood of v. The global offensive k-alliance number γₒ^k(G) is the minimum cardinality of a global offensive k-alliance in G. We present different bounds on γₒ^k(G) in terms of order, maximum degree, independence number, chromatic number and minimum degree.
Keywords: global offensive k-alliance number, independence number, chromatic number 
@article{DMGT_2009_29_3_a10,
     author = {Chellali, Mustapha and Haynes, Teresa and Randerath, Bert and Volkmann, Lutz},
     title = {Bounds on the global offensive k-alliance number in graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {597--613},
     publisher = {mathdoc},
     volume = {29},
     number = {3},
     year = {2009},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2009_29_3_a10/}
}
TY  - JOUR
AU  - Chellali, Mustapha
AU  - Haynes, Teresa
AU  - Randerath, Bert
AU  - Volkmann, Lutz
TI  - Bounds on the global offensive k-alliance number in graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2009
SP  - 597
EP  - 613
VL  - 29
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2009_29_3_a10/
LA  - en
ID  - DMGT_2009_29_3_a10
ER  - 
%0 Journal Article
%A Chellali, Mustapha
%A Haynes, Teresa
%A Randerath, Bert
%A Volkmann, Lutz
%T Bounds on the global offensive k-alliance number in graphs
%J Discussiones Mathematicae. Graph Theory
%D 2009
%P 597-613
%V 29
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2009_29_3_a10/
%G en
%F DMGT_2009_29_3_a10
Chellali, Mustapha; Haynes, Teresa; Randerath, Bert; Volkmann, Lutz. Bounds on the global offensive k-alliance number in graphs. Discussiones Mathematicae. Graph Theory, Tome 29 (2009) no. 3, pp. 597-613. http://geodesic.mathdoc.fr/item/DMGT_2009_29_3_a10/

[1] M. Blidia, M. Chellali and O. Favaron, Independence and 2-domination in trees, Australas. J. Combin. 33 (2005) 317-327.

[2] M. Blidia, M. Chellali and L. Volkmann, Some bounds on the p-domintion number in trees, Discrete Math. 306 (2006) 2031-2037, doi: 10.1016/j.disc.2006.04.010.

[3] R.L. Brooks, On colouring the nodes of a network, Proc. Cambridge Philos. Soc. 37 (1941) 194-197, doi: 10.1017/S030500410002168X.

[4] M. Chellali, Offensive alliances in bipartite graphs, J. Combin. Math. Combin. Comput., to appear.

[5] O. Favaron, G. Fricke, W. Goddard, S.M. Hedetniemi, S.T. Hedetniemi, P. Kristiansen, R.C. Laskar and D.R. Skaggs, Offensive alliances in graphs, Dicuss. Math. Graph Theory 24 (2004) 263-275, doi: 10.7151/dmgt.1230.

[6] O. Favaron, A. Hansberg and L. Volkmann, On k-domination and minimum degree in graphs, J. Graph Theory 57 (2008) 33-40, doi: 10.1002/jgt.20279.

[7] H. Fernau, J.A. Rodríguez and J.M. Sigarreta, Offensive r-alliance in graphs, Discrete Appl. Math. 157 (2009) 177-182, doi: 10.1016/j.dam.2008.06.001.

[8] J.F. Fink, M.S. Jacobson, L.F. Kinch and J. Roberts, On graphs having domination number half their order, Period. Math. Hungar. 16 (1985) 287-293, doi: 10.1007/BF01848079.

[9] J. Fujisawa, A. Hansberg, T. Kubo, A. Saito, M. Sugita and L. Volkmann, Independence and 2-domination in bipartite graphs, Australas. J. Combin. 40 (2008) 265-268.

[10] A. Hansberg, D. Meierling and L. Volkmann, Independence and p-domination in graphs, submitted.

[11] P. Kristiansen, S. M. Hedetniemi and S. T. Hedetniemi, Alliances in graphs, J. Combin. Math. Combin. Comput. 48 (2004) 157-177.

[12] O. Ore, Theory of Graphs (Amer. Math. Soc. Colloq. Publ. 38, 1962).

[13] C. Payan and N.H. Xuong, Domination-balanced graphs, J. Graph Theory 6 (1982) 23-32, doi: 10.1002/jgt.3190060104.

[14] K. H. Shafique and R.D. Dutton, Maximum alliance-free and minimum alliance-cover sets, Congr. Numer. 162 (2003) 139-146.

[15] K. H. Shafique and R.D. Dutton, A tight bound on the cardinalities of maximum alliance-free and minimum alliance-cover sets, J. Combin. Math. Combin. Comput. 56 (2006) 139-145.