On global (strong) defensive alliances in some product graphs

Document Type : Original paper

Authors

1 University of Cadiz

2 University of Maribor

3 Universitat Rovira i Virgili

Abstract

A defensive alliance in a graph is a set $S$ of vertices with the property that every vertex in $S$ has at most one more neighbor outside of $S$ than it has inside of $S$. A defensive alliance $S$ is called global if it forms a dominating set. The global defensive alliance number of a graph $G$ is the minimum cardinality of a global defensive alliance in $G$. In this article we study the global defensive alliances in Cartesian product graphs, strong product graphs and direct product graphs. Specifically we give several bounds for the global defensive alliance number of these graph products and express them in terms of the global defensive alliance numbers of the factor graphs.

Keywords

Main Subjects

References

[1] S. Bermudo, J.A. Rodríguez-Velázquez, J.M. Sigarreta, and I.G. Yero, On global offensive k-alliances in graphs, Appl. Math. Lett. 23 (2010), no. 12, 1454–1458.
[2] R.C. Brigham, R.D. Dutton, and S.T. Hedetniemi, A sharp lower bound on the powerful alliance number of CmCn, Congr. Numer. 167 (2004), 57–63.
[3] R.C. Brigham, R.D. Dutton, and S.T. Hedetniemi, Security in graphs, Discrete Appl. Math. 155 (2007), no. 13, 1708–
1714.
[4] R.D. Dutton, On a graphs security number, Discrete Math. 309 (2009), no. 13, 4443–4447.
[5] R.D. Dutton, R. Lee, and R.C. Brigham, Bounds on a graph’s security number, Discrete Appl. Math. 156 (2008), no. 5, 695–704.
[6] O. Favaron, G. Fricke, W. Goddard, S.M. Hedetniemi, S.T. Hedetniemi, P. Kristiansen, R.C. Laskar, and R.D. Skaggs, Offensive alliances in graphs, Discuss. Math. Graph Theory 24 (2004), no. 2, 263–275.
[7] H. Fernau and J.A. Rodríguez-Velázquez, A survey on alliances and related parameters in graphs, Electronic Journal of Graph Theory and Applications 2 (2014), no. 1, 70–86.
[8] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Fundamentals of domination in graphs, CRC Press, 1998.
[9] K. Kozawa, Y. Otachi, and K. Yamazaki, Security number of grid-like graphs, Discrete Appl. Math. 157 (2009), no. 11, 2555–2561.
[10] P. Kristiansen, S. M Hedetniemi, and S.T. Hedetniemi, Alliances in graphs, J. Combin. Math. Combin. Comput. 48 (2004), 157–178.
[11] D. Kuziak, I. Peterin, and I.G. Yero, Open k-monopolies in graphs: complexity and related concepts, Discrete Math. Theor. Comput. Sci. 18 (2016), no. 3, #6.
[12] J.A. Rodríguez-Velázquez and J.M. Sigarreta, Global defensive k-alliances in graphs, Discrete Appl. Math. 157 (2009), no. 2, 211–218.
[13] J.A. Rodríguez-Velázquez and J.M. Sigarreta, Global defensive k-alliances in graphs, Discrete Appl. Math. 157 (2009), no. 2, 211–218.
[14] K.H. Shafique and R.D. Dutton, Maximum alliance-free and minimum alliance-cover sets, Congr. Numer. 162 (2002), 293–297.
[15] 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.
[16] J. Sigarreta, Upper k-alliances in graphs, Int. J. Contemp. Math. Sciences 6 (2011), no. 43, 2121–2128.
[17] J. Sigarreta, I.G. Yero, S. Bermudo, and J.A. Rodríguez-Velázquez, Partitioning a graph into offensive k-alliances, Discrete Appl. Math. 159 (2011), no. 4, 224–231.
[18] I.G. Yero, S. Bermudo, J.A. Rodríguez-Velázquez, and J. Sigarreta, Partitioning a graph into defensive k-alliances, Acta Math. Sin. (Engl. Ser.) 27 (2011), no. 1, 73–82.
[19] I.G. Yero, M. Jakovac, and D. Kuziak, The security number of strong gridlike graphs, Theoret. Comput. Sci. 653 (2016), 1–14.
[20] I.G. Yero and J.A. Rodríguez-Velázquez, Computing global offensive alliances in cartesian product graphs, Discrete Appl. Math. 161 (2013), no. 1, 284–293.
[21] I.G. Yero and J.A. Rodríguez-Velázquez, A survey on alliances in graphs: Defensive alliances, Util. Math. (accepted).
Communications in Combinatorics and Optimization
Volume 2, Issue 1
June 2017
Pages 21-33

Files

Share

How to cite

Statistics