Secure domination of mesh and pyramid networks

Thomas, Merlin; Cynthia, V. Jude Annie; Prabhu, S.; Rajan, R. Sundara

doi:10.47974/JDMSC-2392

Open Access Research Article

Secure domination of mesh and pyramid networks

^*Merlin ThomasCorresponding authormerlinthomas2526@gmail.comDepartment of MathematicsStella Maris College (Autonomous)Affiliated to University of MadrasChennai, Tamil Nadu, 600086, IndiaView full profile → , V. Jude Annie Cynthiajudeanniecynthia@stellamariscollege.edu.inDepartment of MathematicsStella Maris College (Autonomous)Affiliated to University of MadrasChennai, Tamil Nadu, 600086, IndiaView full profile → , S. Prabhudrsavariprabhu@gmail.comDepartment of MathematicsRajalakshmi Engineering CollegeChennai, Tamil Nadu, 602105, IndiaView full profile → , R. Sundara Rajanvprsundar@gmail.comDepartment of MathematicsRajalakshmi Engineering CollegeChennai, Tamil Nadu, 602105, India0000-0002-1851-6334View full profile →

* Corresponding author · click or hover a name for details

pp. 2211–2221Vol. 29Issue 6June 2026DOI: 10.47974/JDMSC-2392 Crossmark XML

Received:: 01 May 2025
Published Online:: 13 Jun 2026
Article type:: Research Article
Language:: EN
Article no.:: JDMSC-2392
Pages:: 2211–2221

Abstract

Given a dominating set S ⊆ V(G) for a graph G, each vertex of the graph is either in S or is adjacent to at least one vertex in S. The set S is a secure dominating set of G if, for each vertex u ∈ V(G)\S, there exists a vertex w ∈ S adjacent to u such that (S\{w})∪{u} is also a dominating set of G. The minimum cardinality of a secure dominating set in G determines the secure domination number of G. A prior investigation has established an upper bound for the secure domination number of Pp × Pq. Also, the exact values of the secure domination numbers of P2 × Pn and P3 × Pn have been reported in the literature. We present an improved upper bound for the secure domination number of Pn × Pn, when n ≥ 4 and n ≡ s (mod 3), where s ∈ {1, 2}. Using the improved upper bound, we provide an upper bound for the secure domination number of pyramid networks.

Keywords

Secure domination Mesh networks Pyramid networks

Subject Classifications

05C6905C38

References

[1] E. J. Cockayne, P. J. P. Grobler, W. R. Grundlingh, J. Munganga, and J. H. van Vuuren, “Protection of a graph,” Utilitas Mathematica, vol. 67, pp. 19-32 (2005).
[2] H. B. Merouane and M. Chellali, “On secure domination in graphs,” Information Processing Letters, vol. 115, no. 10, pp. 786-790 (2015).
[3] H. Wang, Y. Zhao, and Y. Deng, “The complexity of secure domination problem in graphs,” Discussiones Mathematicae Graph Theory, vol. 38, no. 2, pp. 385-396 (2018).
[4] A. P. Burger, M. A. Henning, and J. H. van Vuuren, “Vertex covers and secure domination in graphs,” Quaestiones Mathematicae, vol. 31, no. 2, pp. 163-171 (2008).
[5] A. P. Burger, A. P. de Villiers, and J. H. van Vuuren, “On minimum secure dominating sets of graphs,” Quaestiones Mathematicae, vol. 39, no. 2, pp. 189-202 (2016).
[6] P. J. P. Grobler and C. M. Mynhardt, “Secure domination critical graphs,” Discrete Mathematics, vol. 309, no. 19, pp. 5820-5827 (2009).
[7] E. J. Cockayne, O. Favaron, and C. M. Mynhardt, “Secure domination, weak Roman domination and forbidden subgraphs,” Bulletin of the Institute of Combinatorics and its Applications, vol. 39, pp. 87-100 (2003).
[8] E. J. Cockayne, “Irredundance, secure domination and maximum degree in trees,” Discrete Mathematics, vol. 307, no. 1, pp. 12-17 (2007).
[9] W. F. Klostermeyer and C. M. Mynhardt, “Secure domination and secure total domination in graphs,” Discussiones Mathematicae Graph Theory, vol. 28, no. 2, pp. 267-284 (2008).
[10] Z. Li and J. Xu, “A characterization of trees with equal independent domination and secure domination numbers,” Information Processing Letters, vol. 119, pp. 14-18 (2017).
[11] D. Pradhan and A. Jha, “On computing a minimum secure dominating set in block graphs,” Journal of Combinatorial Optimization, vol. 35, no. 2, pp. 613–631 (2018), doi: 10.1007/s10878-017-0197-y.
[12] P. R. L. Pushpam and C. Suseendran, “Further results on secure restrained domination in graphs,” Journal of Discrete Mathematical Sciences and Cryptography, vol. 19, no. 2, pp. 277-291 (2016).
[13] I. Boufelgha, M. Ahmia, and M. Guettiche, “Secure 2-domination in graphs,” Journal of Discrete Mathematical Sciences and Cryptography, vol. 28, no. 7, pp. 2723-2736 (2025).
[14] W. F. Klostermeyer, “A dynamic domination problem,” Journal of Discrete Mathematical Sciences and Cryptography, vol. 18, no. 6, pp. 837-848 (2015).
[15] S. Arulanand, R. S. Rajan, S. Prabhu, and S. Stephen, “Certain domination numbers for Cartesian product of graphs,” Journal of Discrete Mathematical Sciences and Cryptography, vol. 27, no. 3, pp. 1045-1058 (2024).
[16] M. Haythorpe and A. Newcombe, “The secure domination number of Cartesian products of small graphs with paths and cycles,” Discrete Applied Mathematics, vol. 309, pp. 32-45 (2022).
[17] J. M. Xu, Topological Structure and Analysis of Interconnection Networks, Springer, New York, USA, (2013), doi: 10.1007/978-1-4757-3387-7.
[18] R. Miller and Q. F. Stout, “Data movement techniques for the pyramid computer,” SIAM Journal on Computing, vol. 16, no. 1, pp. 38-60 (1987).

Views: 355Downloads: 178Citations: 0