Outer-Independent Roman Domination on Cartesian Product of Paths

Abstract:

      Outer-independent Roman domination on graphs originates from the defensive strategy of Ancient Rome, which is that if any city without an army is attacked, a neighboring city with two armies could mobilize an army to support it and any two cities that have no army cannot be adjacent. The outer-independent Roman domination on graphs is an attractive topic in graph theory, and the definition is described as follows. Given a graph $G = (V, E)$, a function $f: V (G) \rightarrow \{0, 1, 2\}$ is an outer-independent Roman dominating function (OIRDF) if $f$ satisfies that every vertex $v \in V$ with $f(v) = 0$ has at least one adjacent vertex $u \in N(v)$ with $f(u) = 2$, where $N(v)$ is the open neighborhood of $v$, and the set $V_0=\{v|f(v)=0\}$ is an independent set. The weight of an OIRDF $f$ is $w(f) = \sum_{v\in V} f(v)$. The value of $\min_f w(f)$ is the outer-independent Roman domination number of $G$, denoted as $\gamma_{oiR}(G)$. This paper is devoted to the study of the outer-independent Roman domination number of the Cartesian product of paths $P_{n}\Box P_{m}$. With the help of computer, we find some recursive OIRDFs and then we present an upper bound of $\gamma_{oiR}(P_{n}\Box P_{m})$. Furthermore, we prove the lower bound of $\gamma_{oiR}(P_{n}\Box P_{m})~(n\le 3)$ is equal to the upper bound. Hence, we achieve the exact value of $\gamma_{oiR}(P_{n}\Box P_{m})$ for $n\le 3$ and the upper bound of $\gamma_{oiR}(P_{n}\Box P_{m})$ for $n\ge 4$.