Discussiones Mathematicae Graph Theory 31(4) (2011)
699-707

doi: 10.7151/dmgt.1574

Lutz Volkmann
Lehrstuhl II für Mathematik |

In this paper we characterize connected graphs G with γ_{o}^{k,c}(G) = n(G). In the case that δ(G) ≥ k ≥ 2, we also characterize the family
of connected graphs G with γ_{o}^{k,c}(G) = n(G) −1. Furthermore, we
present different tight bounds of γ_{o}^{k,c}(G).

**Keywords:** alliances in graphs, connected global offensive *k*-alliance, global offensive *k*-alliance, domination

**2010 Mathematics Subject Classification:** 05C69.

[1] | S. Bermudo, J.A. Rodriguez-Velázquez, J.M. Sigarreta and I.G. Yero, On global offensive , Appl. Math. Lett. k-alliances in graphs 23 (2010) 1454--1458, doi: 10.1016/j.aml.2010.08.008. |

[2] | M. Chellali, Trees with equal global offensive , Opuscula Math. k-alliance and k-domination numbers 30 (2010) 249--254. |

[3] | M. Chellali, T.W. Haynes, B. Randerath and L. Volkmann, Bounds on the global offensive , Discuss. Math. Graph Theory k-alliance number in graphs 29 (2009) 597--613, doi: 10.7151/dmgt.1467. |

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

[5] | J.F. Fink and M.S. Jacobson, , in: Graph Theory with Applications to Algorithms and Computer Science (John Wiley and Sons, New York, 1985) 283--300.n-domination in graphs |

[6] | J.F. Fink and M.S. Jacobson, On , in: Graph Theory with Applications to Algorithms and Computer Science (John Wiley and Sons, New York, 1985) 301--311.n-domination, n-dependence and forbidden subgraphs |

[7] | T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998). |

[8] | T.W. Haynes, S.T. Hedetniemi, and P.J. Slater , Domination in Graphs: Advanced Topics ( Marcel Dekker, New York , 1998). |

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

[10] | O. Ore, Theory of graphs (Amer. Math. Soc. Colloq. Publ. 38 Amer. Math. Soc., Providence, R1, 1962). |

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

[12] | 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 11 June 2010

Revised 5 November 2010

Accepted 5 November 2010