International Journal of Mathematics Trends and Technology
Volume 69 | Issue 10 | Year 2023 | Article Id. IJMTT-V69I10P503 | DOI : https://doi.org/10.14445/22315373/IJMTT-V69I10P503
| Received | Revised | Accepted | Published |
|---|---|---|---|
| 19 Aug 2023 | 26 Sep 2023 | 16 Oct 2023 | 31 Oct 2023 |
For a nontrivial connected graph G with no isolated vertex, a nonempty subset S of the vertex set of G is a safe dominating set if and only if it is both secure and dominating. Moreover, S is called a minimum safe dominating set if S is a safe dominating set of the smallest size in a given graph. The cardinality of the minimum safe dominating set of G is the safe domination number of G. In this paper, we extend the idea of safe and dominating sets by providing characterizations of the safe dominating sets of some graph families. In particular, this paper discusses the minimum cardinality of safe dominating sets of path, cycle, complete, and complete bipartite graphs.
[1] Cabrera Martínez, Abel, et al. "On the Secure Total Domination Number of Graphs." Symmetry, vol. 11, no. 9, 2019, p. 1165,
[CrossRef] [Publisher Link]
[2] Gary Chartrand, Linda Lesniak, and Ping Zhang, Graphs and Digraphs, (Discrete Mathematics and Its Applications), 6th ed., Chapman and Hall/CRC, 2015.
[Publisher Link]
[3] Grobler, P.J.P., and C.M. Mynhardt. "Secure Domination Critical Graphs." Discrete Mathematics, vol. 309, no. 19, 2009, pp. 5820-5827,
[CrossRef] [Publisher Link]
[4] Hernández-Ortiz, R., Montejano, L.P. & Rodríguez-Velázquez, J.A. Secure domination in rooted product graphs. J Comb Optim 41, 401– 413 (2021).
[CrossRef] [Publisher Link]
[5] Jha, Anupriya, et al. "The Secure Domination Problem in Cographs." Information Processing Letters, vol. 145, 2019, pp. 30-38.
[CrossRef] [Publisher Link]
[6] Nathann Cohen et al., “Safe Sets in Graphs: Graph Classes and Structural Parameters,” COCOA 2016 - 10th International Conference Combinatorial Optimization and Applications, Hong Kong, China, pp. 241-253, 2016.
[Google Scholar] [Publisher Link]
[7] Saeid Alikhani, and Yee-Hock Peng, “Dominating Sets and Domination Polynomials of Paths,” International Journal of Mathematics and Mathematical Sciences, vol. 2009, 2009.
[CrossRef] [Google Scholar] [Publisher Link]
[8] Shinya Fujita, Gary MacGillivray, and Tadashi Sakuma, “Safe Set Problem on Graphs,” Discrete Applied Mathematics, vol. 215, pp. 106- 111, 2016.
[CrossRef] [Google Scholar] [Publisher Link]
[9] V. R. Kulli, B. Chaluvaraju & M. Kumara (2018) Graphs with equal secure total domination and inverse secure total domination numbers, Journal of Information and Optimization Sciences, vol. 39, no. 2, pp. 467-473.
[CrossRef] [Publisher Link]
[10] Yun-Hao Zou, Jia-Jie Liu, Shun-Chieh Chang, and Chiun-Chieh Hsu. 2022. The co-secure domination in proper interval graphs. Discrete Appl. Math. 311, C (Apr 2022), 68–71.
[CrossRef] [Publisher Link]
Isagani S. Cabahug Jr., Devine Fathy Mae S. Griño, Marsha Ella L. Maceren, "Introducing Safe Domination in Graphs," International Journal of Mathematics Trends and Technology (IJMTT), vol. 69, no. 10, pp. 17-24, 2023. Crossref, https://doi.org/10.14445/22315373/IJMTT-V69I10P503
PDF 
Abstract 
Keywords 
References 
Citation