# Connected global offensive k-alliances in graphs

Discussiones Mathematicae Graph Theory (2011)

- Volume: 31, Issue: 4, page 699-707
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topLutz Volkmann. "Connected global offensive k-alliances in graphs." Discussiones Mathematicae Graph Theory 31.4 (2011): 699-707. <http://eudml.org/doc/270888>.

@article{LutzVolkmann2011,

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 $γₒ^\{k,c\}(G)$ is the minimum cardinality of a connected global offensive k-alliance in G.
In this paper we characterize connected graphs G with $γₒ^\{k,c\}(G) = n(G)$. In the case that δ(G) ≥ k ≥ 2, we also characterize the family of connected graphs G with $γₒ^\{k,c\}(G) = n(G) - 1$. Furthermore, we present different tight bounds of $γₒ^\{k,c\}(G)$.},

author = {Lutz Volkmann},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {alliances in graphs; connected global offensive k-alliance; global offensive k-alliance; domination; connected global offensive -alliance; global offensive -alliance},

language = {eng},

number = {4},

pages = {699-707},

title = {Connected global offensive k-alliances in graphs},

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

volume = {31},

year = {2011},

}

TY - JOUR

AU - Lutz Volkmann

TI - Connected global offensive k-alliances in graphs

JO - Discussiones Mathematicae Graph Theory

PY - 2011

VL - 31

IS - 4

SP - 699

EP - 707

AB - 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 $γₒ^{k,c}(G)$ is the minimum cardinality of a connected global offensive k-alliance in G.
In this paper we characterize connected graphs G with $γₒ^{k,c}(G) = n(G)$. In the case that δ(G) ≥ k ≥ 2, we also characterize the family of connected graphs G with $γₒ^{k,c}(G) = n(G) - 1$. Furthermore, we present different tight bounds of $γₒ^{k,c}(G)$.

LA - eng

KW - alliances in graphs; connected global offensive k-alliance; global offensive k-alliance; domination; connected global offensive -alliance; global offensive -alliance

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

ER -

## References

top- [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. Zbl1208.05096
- [2] M. Chellali, Trees with equal global offensive k-alliance and k-domination numbers, Opuscula Math. 30 (2010) 249-254. Zbl1238.05191
- [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. Zbl1194.05115
- [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. Zbl1200.05157
- [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). Zbl0890.05002
- [8] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Domination in Graphs: Advanced Topics ( Marcel Dekker, New York, 1998). Zbl0883.00011
- [9] P. Kristiansen, S.M. Hedetniemi and S.T. Hedetniemi, Alliances in graphs, J. Combin. Math. Combin. Comput. 48 (2004) 157-177. Zbl1051.05068
- [10] O. Ore, Theory of graphs (Amer. Math. Soc. Colloq. Publ. 38 Amer. Math. Soc., Providence, R1, 1962). Zbl0105.35401
- [11] K.H. Shafique and R.D. Dutton, Maximum alliance-free and minimum alliance-cover sets, Congr. Numer. 162 (2003) 139-146. Zbl1046.05060
- [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. Zbl1103.05068

## NotesEmbed ?

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