Introducing Safe Domination in Graphs

Isagani S. Cabahug Jr.; Devine Fathy Mae S. Griño; Marsha Ella L. Maceren

doi:https://doi.org/10.14445/22315373/IJMTT-V69I10P503

International Journal of Mathematics Trends and Technology

Research Article | Open Access | Download PDF

Volume 69 | Issue 10 | Year 2023 | Article Id. IJMTT-V69I10P503 | DOI : https://doi.org/10.14445/22315373/IJMTT-V69I10P503

Introducing Safe Domination in Graphs

Isagani S. Cabahug Jr., Devine Fathy Mae S. Griño, Marsha Ella L. Maceren

Received	Revised	Accepted	Published
19 Aug 2023	26 Sep 2023	16 Oct 2023	31 Oct 2023

Citation :

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

Abstract

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.

Keywords

- Domination, Safe domination, Safe domination number, Safe dominating set

References

[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]