Skip to main content
SpringerLink
Log in

Distribution of global defensive k-alliances over some graph products

  • Original Paper
  • Published:
Central European Journal of Operations Research Aims and scope Submit manuscript

Abstract

If \(G=(V_G, E_G)\) is a graph, then \(S\subseteq V_G\) is a global defensive k-alliance in G if (i) each vertex not in S has a neighbor in S and (ii) each vertex of S has at least k more neighbors inside S than outside of it. The global defensive k-alliance number of G is the minimum cardinality among all global defensive k-alliance in G. In this paper this concept is studied on the generalized hierarchical, the lexicographic, the corona, and the edge corona product. For all of these products upper bounds expressed with related invariants of the factors are given. Sharpness of the bounds is also discussed.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2

Similar content being viewed by others

References

  • Anderson SE, Guo Y, Tenney A, Wash KA (2017) Prime factorization and domination in the hierarchical product of graphs. Discuss Math Graph Theory 37:873–890

    Article  Google Scholar 

  • Anderson SE, Nagpal S, Wash K (2018) Domination in the hierarchical product and Vizing’s conjecture. Discrete Math 341:20–24

    Article  Google Scholar 

  • Arezoomand M, Taeri B (2010) Applications of generalized hierarchical product of graphs in computing the Szeged index of chemical graphs. MATCH Commun Math Comput Chem 64:591–602

    Google Scholar 

  • Barrière L, Dalfó C, Fiol MA, Mitjana M (2009) The generalized hierarchical product of graphs. Discrete Math 309:3871–3881

    Article  Google Scholar 

  • Brandstadt A, Le VB, Spinrad JP (1999) Graph classes: a survey. SIAM, Philadelphia

    Book  Google Scholar 

  • Eballe RG, Aldema RM, Paluga EM, Rulete RF, Jamil FP (2012) Global defensive alliances in the join, corona and composition of graphs. Ars Comb. 107:225–245

    Google Scholar 

  • Frucht R, Harary F (1970) On the coronas of two graphs. Aequationes Math 4:322–324

    Article  Google Scholar 

  • Hammack R, Imrich W, Klavžar S (2011) Handbook of product graphs, 2nd edn. CRC Press, Boca Raton

    Book  Google Scholar 

  • Haynes TW, Hedetniemi ST, Slater PJ (1998) Fundamentals of domination in graphs. Marcel Dekker, New York

    Google Scholar 

  • Haynes TW, Knisley D, Seier E, Zou Y (2006) A quantitative analysis of secondary RNA structure using domination based parameters on trees. BMC Bioinform 7:108

    Article  Google Scholar 

  • Hou Y, Shiu W-C (2010) The spectrum of the edge corona of two graphs. Electron J Linear Algebra 20:586–594

    Article  Google Scholar 

  • Kratochvíl J (1986) Perfect codes over graphs. J Comb Theory Ser B 40:224–228

    Article  Google Scholar 

  • Kristiansen P, Hedetniemi SM, Hedetniemi ST (2004) Alliances in graphs. J Comb Math Comb Comput 48:157–177

    Google Scholar 

  • Rinurwati S, Suprajitno H (2016) General results of local metric dimensions of edge-corona of graphs. Int Math Forum 11:793–799

    Article  Google Scholar 

  • Rodríguez-Velázquez JA, Sigarreta JM (2009) Global defensive \(k\)-alliances in graphs. Discrete Appl Math 157:211–218

    Article  Google Scholar 

  • Shafique KH, Dutton RD (2002) On satisfactory partitioning of graphs. Congr Numer 154:183–194

    Google Scholar 

  • Tavakoli M, Rahbarnia F, Ashrafi AR (2014) Applications of the generalized hierarchical product of graphs in computing the vertex and edge PI indices of chemical graphs. Ric Mat 63:59–65

    Article  Google Scholar 

  • Tavakoli M, Rahbarnia F, Ashrafi AR (2014) Studying the corona product of graphs under some graph invariants. Trans Comb 3:43–49

    Google Scholar 

  • Yeh Y-N, Gutman I (1994) On the sum of all distances in composite graphs. Discrete Math 135:359–365

    Article  Google Scholar 

  • Yero IG, Rodríguez-Velázquez JA (2013) Computing global offensive alliances in Cartesian product graphs. Discrete Appl Math 161:284–293

    Article  Google Scholar 

  • Yero IG, Rodríguez-Velázquez JA (2017) A survey on alliances in graphs: defensive alliances. Util Math 105:141–172

    Google Scholar 

  • Yero IG, Bermudo S, Rodríguez-Velázquez JA, Sigarreta JM (2011) Partitioning a graph into defensive \(k\)-alliances. Acta Math Sin (Engl Ser) 27:73–82

    Article  Google Scholar 

  • Yero IG, Jakovac M, Kuziak D (2017) On global (strong) defensive alliances in some product graphs. Commun Comb Optim 2:21–33

    Google Scholar 

Download references

Acknowledgements

Sandi Klavžar acknowledges the financial support from the Slovenian Research Agency (research core funding No. P1-0297 and projects J1-7110, J1-9109, N1-0043). The authors are indebted to the referees for helpful remarks which leaded us to correct and improve the paper.

Author information

Authors and Affiliations

  1. Department of Applied Mathematics, Faculty of Mathematical Sciences, Ferdowsi University of Mashhad, P.O. Box 1159, Mashhad, 91775, Iran

    Mostafa Tavakoli

  2. Faculty of Mathematics and Physics, University of Ljubljana, Ljubljana, Slovenia

    Sandi Klavžar

  3. Faculty of Natural Sciences and Mathematics, University of Maribor, Maribor, Slovenia

    Sandi Klavžar

  4. Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia

    Sandi Klavžar

Authors
  1. Mostafa Tavakoli
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Sandi Klavžar
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Mostafa Tavakoli.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Tavakoli, M., Klavžar, S. Distribution of global defensive k-alliances over some graph products. Cent Eur J Oper Res 27, 615–623 (2019). https://doi.org/10.1007/s10100-018-00605-w

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10100-018-00605-w

Keywords

Mathematics Subject Classification

Search

Navigation