Outer Independent Roman Domination Number of Cartesian Product of Paths and Cycles

Abstract

Given a graph $G$ with vertex set $V$, an outer independent Roman dominating function (OIRDF) is a function $f$ from $V(G)$ to $\{0,1,2\}$ for which every vertex with label $0$ under $f$ is adjacent to at least a vertex with label $2$ but not adjacent to another vertex with label $0$. The weight of an OIRDF $f$ is the sum of vertex function values all over the graph, and the minimum of an OIRDF is the outer independent Roman domination number of $G$, denoted as ${\gamma }_{oiR}(G)$. In this paper, we focus on the outer independent Roman domination number of the Cartesian product of paths and cycles $P_n\square C_m$. We determine the exact values of ${\gamma }_{oiR}(P_n\square C_m)$ for $n=1,2,3$ and ${\gamma }_{oiR}(P_n\square C_3)$ and present an upper bound of ${\gamma }_{oiR}(P_n\square C_m)$ for $n\ge 4,m\ge 4$.