# Bounds on the global offensive k-alliance number in graphs

Mustapha Chellali; Teresa W. Haynes; Bert Randerath; Lutz Volkmann

Discussiones Mathematicae Graph Theory (2009)

- Volume: 29, Issue: 3, page 597-613
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topMustapha Chellali, et al. "Bounds on the global offensive k-alliance number in graphs." Discussiones Mathematicae Graph Theory 29.3 (2009): 597-613. <http://eudml.org/doc/270797>.

@article{MustaphaChellali2009,

abstract = {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.},

author = {Mustapha Chellali, Teresa W. Haynes, Bert Randerath, Lutz Volkmann},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {global offensive k-alliance number; independence number; chromatic number; global offensive -alliance number},

language = {eng},

number = {3},

pages = {597-613},

title = {Bounds on the global offensive k-alliance number in graphs},

url = {http://eudml.org/doc/270797},

volume = {29},

year = {2009},

}

TY - JOUR

AU - Mustapha Chellali

AU - Teresa W. Haynes

AU - Bert Randerath

AU - Lutz Volkmann

TI - Bounds on the global offensive k-alliance number in graphs

JO - Discussiones Mathematicae Graph Theory

PY - 2009

VL - 29

IS - 3

SP - 597

EP - 613

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

LA - eng

KW - global offensive k-alliance number; independence number; chromatic number; global offensive -alliance number

UR - http://eudml.org/doc/270797

ER -

## References

top- [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. Zbl1100.05069
- [3] R.L. Brooks, On colouring the nodes of a network, Proc. Cambridge Philos. Soc. 37 (1941) 194-197, doi: 10.1017/S030500410002168X. Zbl0027.26403
- [4] M. Chellali, Offensive alliances in bipartite graphs, J. Combin. Math. Combin. Comput., to appear. Zbl1198.05119
- [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. Zbl1064.05112
- [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. Zbl1211.05110
- [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. Zbl1200.05157
- [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. Zbl0602.05043
- [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. Zbl1147.05052
- [10] A. Hansberg, D. Meierling and L. Volkmann, Independence and p-domination in graphs, submitted. Zbl1210.05096
- [11] P. Kristiansen, S. M. Hedetniemi and S. T. Hedetniemi, Alliances in graphs, J. Combin. Math. Combin. Comput. 48 (2004) 157-177. Zbl1051.05068
- [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. Zbl0489.05049
- [14] K. H. Shafique and R.D. Dutton, Maximum alliance-free and minimum alliance-cover sets, Congr. Numer. 162 (2003) 139-146. Zbl1046.05060
- [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. Zbl1103.05068

## Citations in EuDML Documents

top## NotesEmbed ?

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