Independent Perfect Secure Domination in Graphs
Keywords:
Secure dominating set, perfect secure dominating set, independent perfect secure dominating set, computational complexityAbstract
For a graph G = (V, E), a subset Y ⊆ V will be a dominating set if each vertex y ∈ V \Y possesses a neighbour in Y . A perfect secure dominating set of G is a dominating set in which every vertex y ∈ V \Y , has a unique vertex x ∈ Y such that xy ∈ E and (Y \{x})∪ {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 spiders in this paper. The complexity of the parameter is also discussed.
Downloads
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), 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 (Eds.), Topics in domination in graphs, Series: Developments in Mathematics, 64, Springer, Cham (2020), doi:10.1007/978-3-030-51117-3.
T.W. Haynes, S.T. Hedetniemi and M.A. Henning, Domination in graphs: Core concepts, Series: Springer Monographs in Mathematics, Springer, Cham (2023), doi:10.1007/978-3-031-09496-5.
T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in graphs: Volume 2: Advanced topics, Routledge, New York (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.
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 Special Issue on the Occasion of Banaschewski’s 90th Birthday (II) (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.
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.
