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

Abstract

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

How to cite

top

Mustapha 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. [1] M. Blidia, M. Chellali and O. Favaron, Independence and 2-domination in trees, Australas. J. Combin. 33 (2005) 317-327. 
  2. [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. [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. [4] M. Chellali, Offensive alliances in bipartite graphs, J. Combin. Math. Combin. Comput., to appear. Zbl1198.05119
  5. [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. [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. [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. [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. [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. [10] A. Hansberg, D. Meierling and L. Volkmann, Independence and p-domination in graphs, submitted. Zbl1210.05096
  11. [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. [12] O. Ore, Theory of Graphs (Amer. Math. Soc. Colloq. Publ. 38, 1962). 
  13. [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. [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. [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

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.