Discussiones Mathematicae Graph Theory 31(4) (2011) 699-707
doi: 10.7151/dmgt.1574

[BIBTex] [PDF] [PS]

Connected Global Offensive k-alliances in Graphs

Lutz Volkmann

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

Abstract

We consider finite graphs G with vertex set V(G). For a subset S ⊆ V(G), we define by G[S] the subgraph induced by S. By n(G) = |V(G) | and δ(G) we denote the order and the minimum degree of G, respectively. Let k be a positive integer. A subset S ⊆ V(G) is a connected global offensive k-alliance of the connected graph G, if G[S] is connected and |N(v) ∩S | ≥ |N(v) −S |+k for every vertex v ∈ V(G) −S, where N(v) is the neighborhood of v. The connected global offensive k-alliance number γok,c(G) is the minimum cardinality of a connected global offensive k-alliance in G.

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

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

2010 Mathematics Subject Classification: 05C69.

References

[1]S. Bermudo, J.A. Rodriguez-Velázquez, J.M. Sigarreta and I.G. Yero, On global offensive k-alliances in graphs, Appl. Math. Lett. 23 (2010) 1454--1458, doi: 10.1016/j.aml.2010.08.008.
[2]M. Chellali, Trees with equal global offensive k-alliance and k-domination numbers, Opuscula Math. 30 (2010) 249--254.
[3]M. Chellali, T.W. Haynes, B. Randerath and L. Volkmann, Bounds on the global offensive k-alliance number in graphs, Discuss. Math. Graph Theory 29 (2009) 597--613, doi: 10.7151/dmgt.1467.
[4]H. Fernau, J.A. Rodriguez and J.M. Sigarreta, Offensive r-alliance in graphs, Discrete Appl. Math. 157 (2009) 177--182, doi: 10.1016/j.dam.2008.06.001.
[5]J.F. Fink and M.S. Jacobson, n-domination in graphs, in: Graph Theory with Applications to Algorithms and Computer Science (John Wiley and Sons, New York, 1985) 283--300.
[6]J.F. Fink and M.S. Jacobson, On n-domination, n-dependence and forbidden subgraphs, in: Graph Theory with Applications to Algorithms and Computer Science (John Wiley and Sons, New York, 1985) 301--311.
[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