Connected global offensive k-alliances in graphs

Lutz Volkmann

Discussiones Mathematicae Graph Theory (2011)

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

Abstract

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

How to cite

top

Lutz 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. [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. [2] M. Chellali, Trees with equal global offensive k-alliance and k-domination numbers, Opuscula Math. 30 (2010) 249-254. Zbl1238.05191
  3. [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. [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. [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. [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. [7] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998). Zbl0890.05002
  8. [8] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Domination in Graphs: Advanced Topics ( Marcel Dekker, New York, 1998). Zbl0883.00011
  9. [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. [10] O. Ore, Theory of graphs (Amer. Math. Soc. Colloq. Publ. 38 Amer. Math. Soc., Providence, R1, 1962). Zbl0105.35401
  11. [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. [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 ?

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.