Independent Perfect Secure Domination in Certain Cartesian Product Graphs
DOI:
https://doi.org/10.26713/cma.v16i3.3408Keywords:
Independent perfect secure dominating set, Cartesian productAbstract
In a graph \(G=(V(G),E(G))\), a set \(S\subseteq V(G)\) is a dominating set of \(G\) when every vertex in \(V(G)\setminus S\) is adjacent to at least one vertex in \(S\). A dominating set \(S\) is called an independent perfect secure dominating set of \(G\) if \(S\) is an independent set and if for each vertex \(w\in V(G)\setminus S\), there exists a unique vertex \(v\in S\) such that \(v\) is adjacent to \(w\) and \((S\setminus\{v\})\cup\{w\}\) is a dominating set of \(G\). The minimum cardinality of an independent perfect secure dominating set of \(G\) is called the independent perfect secure domination number of \(G\). In this paper, we determine the exact value of the independent perfect secure domination number of \(G\square H\), where \(G\) is a complete graph and \(H\) belongs to specific graph classes such as complete graphs, complete bipartite graphs, paths, and cycles. Upper bounds for the independent perfect secure domination number of certain other Cartesian product graphs are also dealt with in this paper.
Downloads
References
J. A. Bondy and U. S. R. Murty, Graph Theory with Applications, North-Holland, New York, x + 264 pages (1976).
A. P. Burger, A. P. de Villiers and J. H. van Vuuren, On minimum secure dominating sets of graphs, Quaestiones Mathematicae 39(2) (2016), 189 – 202, DOI: 10.2989/16073606.2015.1068238.
A. P. Burger, M. A. Henning and J. H. van Vuuren, Vertex covers and secure domination in graphs, Quaestiones Mathematicae 31(2) (2008), 163 – 171, DOI: 10.2989/QM.2008.31.2.5.477.
P. Chakradhar and P. V. S. Reddy, Complexity issues of perfect secure domination in graphs, RAIRO – Theoretical Informatics and Applications 55 (2021), Article number 11, DOI: 10.1051/ita/2021012.
X. Chen, T. Li and J. Zhang, A note on secure domination number in 2K2-free graphs, Discrete Applied Mathematics 368 (2025), 162 – 164, DOI: 10.1016/j.dam.2025.02.019.
E. J. Cockayne, Irredundance, secure domination and maximum degree in trees, Discrete Mathematics 307(1) (2007), 12 – 17, DOI: 10.1016/j.disc.2006.05.037.
E. J. Cockayne, P. J. P. Grobler, W. R. Grundlingh, J. Munganga and J. H. van Vuuren, Protection of a graph, Utilitas Mathematica 67 (2005), 19 – 32, URL: https://utilitasmathematica.com/index.php/Index/article/view/370.
M. El-Zahar and C. M. Pareek, Domination number of products of graphs, Ars Combinatoria 31 (1991), 223 – 227, URL: https://combinatorialpress.com/article/ars/Volume%20031/volume-31-paper-26.pdf.
P. J. P. Grobler and C. M. Mynhardt, Secure domination critical graphs, Discrete Mathematics 309(19) (2009), 5820 – 5827, DOI: 10.1016/j.disc.2008.05.050.
R. Hammack, W. Imrich and S. Klavžar, Handbook of Product Graphs, CRC Press, Boca Raton, 536 pages (2011), DOI: 10.1201/b10959.
T. W. Haynes, S. T. Hedetniemi and M. A. Henning (editors), Topics in Domination in Graphs, Developments in Mathematics series, Springer, Cham, viii + 545 pages (2020), DOI: 10.1007/978-3-030-51117-3.
T. W. Haynes, S. T. Hedetniemi and M. A. Henning, Domination in Graphs: Core Concepts, Springer Monographs in Mathematics series, Springer, Cham, xx + 644 pages (2023), DOI: 10.1007/978-3-031-09496-5.
M. Haythorpe and A. Newcombe, The secure domination number of Cartesian products of small graphs with paths and cycles, Discrete Applied Mathematics 309 (2022), 32 – 45, DOI: 10.1016/j.dam.2021.11.008.
R. Hernández-Ortiz, L. P. Montejano and J. A. Rodríguez-Velázquez, Secure domination in rooted product graphs, Journal of Combinatorial Optimization 41 (2021), 401 – 413, DOI: 10.1007/s10878-020-00679-w.
W. F. Klostermeyer and C. M. Mynhardt, Secure domination and secure total domination in graphs, Discussiones Mathematicae Graph Theory 28(2) (2008), 267 – 284, DOI: 10.7151/dmgt.1405.
Z. Li and J. Xu, A characterization of trees with equal independent domination and secure domination numbers, Information Processing Letters 119 (2017), 14 – 18, DOI: 10.1016/j.ipl.2016.11.004.
H. B. Merouane and M. Chellali, On secure domination in graphs, Information Processing Letters 115(10) (2015), 786 – 790, DOI: 10.1016/j.ipl.2015.05.006.
S. V. D. Rashmi, S. Arumugam, K. R. Bhutani and P. Gartland, Perfect secure domination in graphs, Categories and General Algebraic Structures with Applications 7(1) (2017), 125 – 140, URL: https://cgasa.sbu.ac.ir/article_44926.html.
M. Thomas and V. J. A. Cynthia, Independent perfect secure domination in graphs, Communications in Mathematics and Applications 16(1) (2025), 339 – 352, URL: https://rgnpublications.com/journals/index.php/cma/article/view/3035.
M. Valveny and J. A. Rodríguez-Velázquez, Protection of graphs with emphasis on Cartesian product graphs, Filomat 33(1) (2019), 319 – 333, URL: https://www.jstor.org/stable/27382287.
H.Wang, Y. Zhao and Y. Deng, The complexity of secure domination problem in graphs, Discussiones Mathematicae Graph Theory 38(2) (2018), 385 – 396, DOI: 10.7151/dmgt.2008.
J. Xu, Topological Structure and Analysis of Interconnection Networks, 1st edition, Network Theory and Applications series, Volume 7, Springer, New York, x + 342 pages (2001), DOI: 10.1007/978-1-4757-3387-7.
Downloads
Published
How to Cite
Issue
Section
License
Authors who publish with this journal agree to the following terms:
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a CCAL that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.
