ArticleOriginal scientific text

Title

Bounds on the global offensive k-alliance number in graphs

Authors 1, 2, 3, 3

Affiliations

  1. LAMDA-RO Laboratory, Department of Mathematics, University of Blida, B.P. 270, Blida, Algeria
  2. Department of Mathematics, East Tennessee State University, Johnson City, TN 37614 USA
  3. Lehrstuhl II für Mathematik, RWTH Aachen University, Templergraben 55, D-52056 Aachen, Germany

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.

Keywords

global offensive k-alliance number, independence number, chromatic number

Bibliography

  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.
Pages:
597-613
Main language of publication
English
Received
2008-07-08
Accepted
2008-12-08
Published
2009
Exact and natural sciences