Perfect Roman and Perfect Italian Domination of Cartesian Product Graphs

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