ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2019: 0.755

SCImago Journal Rank (SJR) 2019: 0.600

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory


Discussiones Mathematicae Graph Theory 29(3) (2009) 597-613
DOI: 10.7151/dmgt.1467


1 Mustapha Chellali,  2Teresa W. Haynes, 3 Bert Randerath  and  3Lutz Volkmann

1LAMDA-RO Laboratory, Department of Mathematics
University of Blida
B.P. 270, Blida, Algeria

2Department of Mathematics
East Tennessee State University
Johnson City, TN 37614 USA

3Lehrstuhl II für Mathematik
RWTH Aachen University
Templergraben 55, D-52056 Aachen, Germany


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 γok(G) is the minimum cardinality of a global offensive k-alliance in G. We present different bounds on γok(G) in terms of order, maximum degree, independence number, chromatic number and minimum degree.

Keywords: global offensive k-alliance number, independence number, chromatic number.

2000 Mathematics Subject Classification: 05C69.


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

Received 8 July 2008
Revised 8 December 2008
Accepted 8 December 2008