Independent Perfect Secure Domination in Graphs

Authors

  • Merlin Thomas Department of Mathematics, Stella Maris College (affiliated to the University of Madras), Chennai, India https://orcid.org/0009-0001-7581-7731
  • V. Jude Annie Cynthia Department of Mathematics, Stella Maris College (affiliated to the University of Madras), Chennai, India https://orcid.org/0000-0002-1470-6413

DOI:

https://doi.org/10.26713/cma.v16i1.3035

Keywords:

Secure dominating set, Perfect secure dominating set, Independent perfect secure dominating set, Computational complexity

Abstract

For a graph \(G=(V,E)\), a subset \(Y\subseteq V\) will be a dominating set if each vertex \(y\in V\backslash Y\) possesses a neighbour in \(Y\). A perfect secure dominating set of \(G\) is a dominating set in which every vertex \(y\in V\backslash Y\), has a unique vertex \(x\in Y\) such that \(xy\in E\) and \((Y\backslash \{x\})\cup \{y\}\) is a dominating set. In addition, if \(Y\) is an independent set, then \(Y\) is an independent perfect secure dominating set of \(G\). We have introduced the concept of independent perfect secure domination, presented the fundamental properties of this new parameter and investigated the independent perfect secure domination in certain classes of graphs such as the connected split graphs and the spiders in this paper. The complexity of the parameter is also discussed.

Downloads

Download data is not yet available.

References

T. Araki and I. Yumoto, On the secure domination numbers of maximal outerplanar graphs, Discrete Applied Mathematics 236 (2018), 23 – 29, DOI: 10.1016/j.dam.2017.10.020.

N. Biggs, Perfect codes in graphs, Journal of Combinatorial Theory, Series B 15(3) (1973), 289 – 296, DOI: 10.1016/0095-8956(73)90042-7.

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.

M. Cary, J. Cary and S. Prabhu, Independent domination in directed graphs, Communications in Combinatorics and Optimization 6(1) (2021), 67 – 80, DOI: 10.22049/cco.2020.26845.1149.

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.

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. A. Dreyer Jr., S. M. Hedetniemi and S. T. Hedetniemi, Roman domination in graphs, Discrete Mathematics 278(1-3) (2004), 11 – 22, DOI: 10.1016/j.disc.2003.06.004.

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.

W. Goddard and M. A. Henning, Independent domination in graphs: A survey and recent results, Discrete Mathematics 313(7) (2013), 839 – 854, DOI: 10.1016/j.disc.2012.11.031.

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.

T. W. Haynes, S. T. Hedetniemi and M. A. Henning (editors), Topics in Domination in Graphs, Developments in Mathematics series, Volume 64, 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.

T. W. Haynes, S. T. Hedetniemi and P. J. Slater, Domination in Graphs: Advanced Topics, Volume 2, Routledge, New York, 520 pages (2017), DOI: 10.1201/9781315141428.

M. A. Henning and S. T. Hedetniemi, Defending the Roman empire – A new strategy, Discrete Mathematics 266(1-3) (2003), 239 – 251, DOI: 10.1016/S0012-365X(02)00811-7.

J.L. Hurink and T. Nieberg, Approximating minimum independent dominating sets in wireless networks, Information Processing Letters 109(2) (2008), 155 – 160, DOI: 10.1016/j.ipl.2008.09.021.

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.

A. A. McRae, Generalizing NP-Completeness Proofs for Bipartite Graphs and Chordal Graphs, Ph.D. Thesis, Clemson University, Clemson, SC (1994).

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 (2017), 125 – 140, URL: https://cgasa.sbu.ac.ir/article_44926.html.

S. Varghese, S. Varghese and A. Vijayakumar, Power domination in Mycielskian of spiders, AKCE International Journal of Graphs and Combinatorics 19(2) (2022), 154 – 158, DOI: 10.1080/09728600.2022.2082900.

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.

Downloads

Published

01-07-2025
CITATION

How to Cite

Thomas, M., & Cynthia, V. J. A. (2025). Independent Perfect Secure Domination in Graphs. Communications in Mathematics and Applications, 16(1), 339–352. https://doi.org/10.26713/cma.v16i1.3035

Issue

Vol. 16 No. 1 (2025)

Section

Research Article

License

Creative Commons Licence 4.0 by  

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.