Perfect Roman and Perfect Italian Domination of Cartesian Product Graphs

(Ahlam Almulhim)

---

Abstract

For a graph G=(V,E), a function f:V→{0,1,2} is a perfect Roman dominating function (PRDF) on G if every v∈V with f(v)=0 is adjacent to exactly one vertex u with f(u)=2. The sum ∑_(v∈V)^▒f (v) is the weight w(f) of f. The perfect Roman domination number γ_R^p (G) of G is least positive integer k such that there is a PRDF f on G with w(f)≤k. A function f:V→{0,1,2} is a perfect Italian dominating function (PIDF) on G if for every v∈V with f(v)=0, ∑_(u∈N(v))^▒f (u)=2. The sum ∑_(v∈V)^▒f (v) is the weight w(f). The perfect Italian domination number γ_I^p (G) of G is least positive integer k such that there is a PIDF f on G with w(f)≤k. Perfect Roman domination and perfect Italian domination are variants of Roman domination, which was originally introduced as a defensive strategy of the Roman Empire. In this article, we prove that the perfect Roman domination and perfect Italian domination problems for Cartesian product graphs are NP-complete. We also give an upper bound for γ_I^p (G), where G is the Cartesian product of paths and cycles.
KEYWORDS
graph domination, graph operations, graph theory, np-completeness, problem complexity, simple graphs

PDF

References

Almulhim, A., Akwu, A.D. and AlSubaiei, B. (2022). The perfect Roman domination number of the Cartesian product of some graphs. Journal of Mathematics, 2022(1), 1957027. DOI:10.1155/2022/1957027
Almulhim, A., AlSubaiei, B. and Monda, S.R. (2024). Survey on Roman {2}-domination. Mathematics, 12(17), 2771. DOI:10.3390/math12172771
Banerjee, S., Henning, M.A. and Pradhan, D. (2021). Perfect Italian domination in cographs. Applied Mathematics and Computation, 391(n/a), 125703. DOI:10.1016/j.amc.2020.125703
Cabrera Martínez, A., García-Gómez, C. and Rodríguez-Velázquez, J.A. (2022). Perfect domination, Roman domination and perfect Roman Domination in lexicographic product graphs. Fundamenta Informaticae, 185(3), 201–20. DOI:10.3233/FI-222108
Chellali, M., Haynes, T.W., Hedetniemi, S.T. and McRae, A.A. (2016). Roman 2-domination. Discrete Applied Mathematics, 204(n/a), 22–8. DOI:10.1016/j.dam.2015.11.013
Cockayne, E.J., Dreyer Jr, P.A., Hedetniemi, S.M. and Hedetniemi, S.T. (2004). Roman domination in graphs. Discrete Mathematics, 278(1-3), 11–22. DOI:10.1016/j.disc.2003.06.004
Darkooti, M., Alhevaz, A., Rahimi, S. and Rahbani, H. (2019). On perfect Roman domination number in trees: Complexity and bounds. Journal of Combinatorial Optimization, 38(n/a), 712–20. DOI:10.1007/s10878-019-00408-y
Johnson, D. S. and Garey, M. R. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. USA, New York City: W. H. Freeman.
Haynes, T.W. and Henning, M.A. (2019). Perfect Italian domination in trees. Discrete Applied Mathematics, 260(n/a), 164–77. DOI:10.1016/j.dam.2019.01.038
Henning, M.A. and Klostermeyer, W.F. (2018). Perfect Roman domination in regular graphs. Applicable Analysis and Discrete Mathematics, 12(1), 143–52. DOI:10.2298/AADM1801143H
Henning, M.A., Klostermeyer, W.F. and MacGillivray, G. (2018). Perfect Roman domination in trees. Discrete Applied Mathematics, 236(n/a), 235–45. DOI:10.1016/j.dam.2017.10.027
Lauri, J. and Mitillos, C. (2020). Perfect Italian domination on planar and regular graphs. Discrete Applied Mathematics, 285(n/a), 676–87. DOI:10.1016/j.dam.2020.05.024
Luiz, A.G. (2024). Roman domination and independent Roman domination on graphs with maximum degree three. Discrete Applied Mathematics, 348(n/a), 260–78. DOI:10.1016/j.dam.2024.02.006
Nazari-Moghaddam, S. and Chellali, M. (2022). A new upper bound for the perfect Italian domination number of a tree. Discussiones Mathematicae Graph Theory, 42(n/a), 1005–22. DOI:10.7151/dmgt.2324
Pradhan, D., Banerjee, S. and Liu, J. B. (2022). Perfect Italian domination in graphs: Complexity and algorithms. Discrete Applied Mathematics, 319(n/a), 271–95. DOI:10.1016/j.dam.2021.08.020
ReVelle, C. S. (1997). Can you protect the Roman Empire. Johns Hopkins Magazine, 49(2), 40.
Revelle, C. and Rosing, K.E. (2000). Defendens Imperium Romanum: A classical problem in military strategy. American Mathematical Monthly, 107(7), 585–94. DOI:10.2307/2589113
Stewart, I. (1999). Defend the Roman Empire! Scientific American, 281(6), 136–8. DOI:10.1038/scientificamerican1299-136