\publyear

22 \papernumber2102

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

Hong Gao^* Daoda Qiu Shuyan Du Yiyue Zhao
College of Science
Dalian Maritime University
Dalian China
[email protected] [email protected] [email protected] [email protected] Yuansheng Yang
School of Computer Science and Technology
Dalian University of Technology
Dalian China
[email protected]

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}\Box C_{m}$ . We determine the exact values of $\gamma_{oiR}(P_{n}\Box C_{m})$ for $n=1,2,3$ and $\gamma_{oiR}(P_{n}\Box C_{3})$ and present an upper bound of $\gamma_{oiR}(P_{n}\Box C_{m})$ for $n\geq 4,m\geq 4$ .

keywords:

outer independent Roman domination, Cartesian product graphs, paths, cycles

^†^†volume: 185^†^†issue: 1

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

1 Introduction

In this paper, $G=(V,E)$ is a simple, undirected and connected graph with vertex set $V$ and edge set $E$ . For a vertex $v\in V$ , the open neighbourhood of $v$ is the set $N(v)=\{{u\in V|uv\in E}\}$ and the closed neighbourhood is the set $N[v]=N(v)\cup\{{v}\}$ .

Roman domination on graphs is originated from Roman military strategy in which it is required that every location without legions must be adjacent to at least one location with two legions. In 2004, Cockayne et al. [1] proposed Roman domination on graphs. A Roman dominating function (RDF) on graph $G=(V,E)$ is a function $f:V\rightarrow\{0,1,2\}$ such that for each vertex $u\in V$ with $f(u)=0$ , there exists at least one vertex $v\in N(u)$ with $f(v)=2$ . The weight of a RDF $f$ is $w(f)=\sum_{v\in V}f(v)$ . The Roman domination number is the minimum weight of a RDF of $G$ , denoted as $\gamma_{R}(G)$ . Let $V_{i}=\{v\in V|f(v)=i\}$ for $i\in\{0,1,2\}$ , then a RDF $f$ can be written as $f=(V_{0},V_{1},V_{2})$ .

Roman domination is an attractive topic, and many papers have been published on it [2, 3, 4, 5]. In order to strengthen defense capability or reduce costs, scholars studied many variations of Roman domination, such as double Roman domination [6], Italian domination [7], triple Roman domination [8], perfect Roman domination [9], signed Roman domination [10], and so on.

In Roman domination, if two locations without legions are not adjacent, then the defense capability can be strengthened. In 2017, Ahangar et al. [11] introduced the outer independent Roman domination on graphs. Given a graph $G=(V,E)$ , an outer independent Roman dominating function (OIRDF) $f=(V_{0},V_{1},V_{2})$ is a RDF and $V_{0}$ is independent. The weight of an OIRDF is $w(f)=\sum_{v\in V}f(v)=|V_{1}|+|V_{2}|$ . The outer independent Roman domination number is the minimum weight of an OIRDF of $G$ , denoted as $\gamma_{oiR}(G)$ . An OIRDF $f$ is a $\gamma_{oiR}$ -function if $w(f)=\gamma_{oiR}(G)$ .

Scholars are very interested in this topic and have published many related research results. Martínez et al. [12] obtained some bounds on $\gamma_{oiR}(G)$ in terms of other parameters and provided closed formulas for the outer independent Roman domination number of rooted product graphs. Poureidi et al. [13] proposed an algorithm to compute $\gamma_{oiR}(G)$ in ${\mathcal{O}}(|V|)$ time. Nazari-Moghaddam et al. [14] provided a constructive characterization of trees $T$ whose outer-independent Roman domination number is equal to its Roman domination number. Dehgardi et al. [15] presented an upper bound of $\gamma_{oiR}(T)$ for a tree $T$ of order $n\geq 3$ . Rad et al. [16] presented upper bounds on the outer-independent Roman domination number for unicyclic and bicyclic graphs.

To compute the exact value of the outer independent Roman domination number in Cartesian product graphs is as difficult as to compute its 2-domination number [17]. In this paper, we study the outer independent Roman domination number of the Cartesian product of paths and cycles $P_{n}\Box C_{m}$ . We determine the exact values of $\gamma_{oiR}(P_{n}\Box C_{3})$ and $\gamma_{oiR}(P_{n}\Box C_{m})$ for $n=1,2,3$ . We also present an upper on $\gamma_{oiR}(P_{n}\Box C_{m})$ for $m,n\geq 4$ .

The Cartesian product of paths and cycles is the graph $G=P_{n}\Box C_{m}$ with vertex set $V(G)=\{v_{i,j}|0\leq i\leq n-1,0\leq j\leq m-1\}$ . $G=P_{n}\Box C_{m}$ is a cylindrical graph and is an important network topology structure graph. Figure 1 shows graph $P_{3}\Box C_{4}$ . Let $f:V\rightarrow\{0,1,2\}$ be an OIRDF on $P_{n}\Box C_{m}$ , then we denote $f$ as follows.

\displaystyle\small{f=\left(\begin{array}[]{cccccc}f(v_{0,0})&f(v_{0,1})&\cdots&f(v_{0,m-1})\\ f(v_{1,0})&f(v_{1,1})&\cdots&f(v_{1,m-1})\\ \vdots&\vdots&\ddots&\vdots\\ f(v_{n-1,0})&f(v_{n-1,1})&\cdots&f(v_{n-1,m-1})\end{array}\right).}

Figure 1: Graph

P_{3}\Box C_{4}

2 The outer independent Roman domination number of $P_{1}\Box C_{m}$ , $P_{2}\Box C_{m}$ and $P_{3}\Box C_{m}$

Theorem 2.1

For any integer $m\geq 3$ , $\gamma_{oiR}(P_{1}\Box C_{m})=3\lfloor\frac{m}{4}\rfloor+t$ , where $m\equiv t(\bmod\ 4)$ and $t\in\{0,1,2,3\}$ .

Proof 2.2

Since $P_{1}\Box C_{m}$ and $C_{m}$ are isomorphic (written $P_{1}\Box C_{m}\cong C_{m}$ ), then we can achieve the outer independent Roman domination number of $P_{1}\Box C_{m}$ by the outer independent Roman domination number of $C_{m}$ [11].

Theorem 2.3

For any integer $m\geq 3$ ,

\gamma_{oiR}(P_{2}\Box C_{m})=\left\{\begin{array}[]{lllllllll}\lceil\frac{4m}{3}\rceil+1,&m\equiv 3,5(\bmod\ 6),\\ \lceil\frac{4m}{3}\rceil,&otherwise.\end{array}\right.

Proof 2.4

Let $G=P_{2}\Box C_{m}$ , $V(G)=\{v_{i,j}|0\leq i\leq 1,0\leq j\leq m-1\}$ .

(1) $\gamma_{oiR}(P_{2}\Box C_{m})\leq\lceil\frac{4m}{3}\rceil+1$ for $m\equiv 3,5(\bmod\ 6)$ , $\gamma_{oiR}(P_{2}\Box C_{m})\leq\lceil\frac{4m}{3}\rceil$ otherwise. We first define a function $h$ on $\{v_{i,j}|0\leq i\leq 1,0\leq j\leq 5\}$ .

\displaystyle\small{h(v_{i,j})=\left\{\begin{array}[]{llllll}2,&(i=0\wedge j=0)\vee(i=1\wedge j=3),\\ 1,&(i=0\wedge j=2,4)\vee(i=1\wedge j=1,5),\\ 0,&otherwise.\end{array}\right.\text{\ \ i.e.\ \ }h=\left(\begin{array}[]{llllll}201010\\ 010201\end{array}\right).}

Then we define an OIRDF $f$ on $P_{2}\Box C_{m}$ as follows,

\small{f(v_{i,j})=\left\{\begin{array}[]{llllll}1,&m\equiv 1(\bmod\ 6),i=0,j=m-2,\\ &m\equiv 1,3,5(\bmod\ 6),i=1,j=m-1,\\ 0,&m\equiv 1(\bmod\ 6),i=0,j=m-1,\\ h(v_{i,j\bmod 6}),&otherwise.\end{array}\right.}

That is,

$\displaystyle m$	$\displaystyle\equiv 0\,(\bmod\,6),$	$\displaystyle m$	$\displaystyle\equiv 1\,(\bmod\,6),$
$\displaystyle f$	$\displaystyle=\begin{pmatrix}201010&\cdots&201010\\ 010201&\cdots&010201\end{pmatrix},$	$\displaystyle f$	$\displaystyle=\begin{pmatrix}201010&\cdots&201010&2010110\\ 010201&\cdots&010201&0102011\end{pmatrix}$
$\displaystyle m$	$\displaystyle\equiv 2\,(\bmod\,6),$	$\displaystyle m$	$\displaystyle\equiv 3\,(\bmod\,6),$
$\displaystyle f$	$\displaystyle=\begin{pmatrix}201010&\cdots&201010&20\\ 010201&\cdots&010201&01\end{pmatrix},$	$\displaystyle f$	$\displaystyle=\begin{pmatrix}201010&\cdots&201010&201\\ 010201&\cdots&010201&011\end{pmatrix}$
$\displaystyle m$	$\displaystyle\equiv 4\,(\bmod\,6),$	$\displaystyle m$	$\displaystyle\equiv 5\,(\bmod\,6),$
$\displaystyle f$	$\displaystyle=\begin{pmatrix}201010&\cdots&201010&2010\\ 010201&\cdots&010201&0102\end{pmatrix},$	$\displaystyle f$	$\displaystyle=\begin{pmatrix}201010&\cdots&201010&20101\\ 010201&\cdots&010201&01021\end{pmatrix}$

One can check that $f$ is an OIRDF and the weight of $f$ is

\small{w(f)=\left\{\begin{array}[]{lllllllll}\frac{m}{6}\times 8=\frac{4m}{3},&m\equiv 0(\bmod\ 6),\\ \frac{m-7}{6}\times 8+10=\frac{4m+2}{3},&m\equiv 1(\bmod\ 6),\\ \frac{m-2}{6}\times 8+3=\frac{4m+1}{3},&m\equiv 2(\bmod\ 6),\\ \frac{m-3}{6}\times 8+5=\frac{4m+3}{3},&m\equiv 3(\bmod\ 6),\\ \frac{m-4}{6}\times 8+6=\frac{4m+2}{3},&m\equiv 4(\bmod\ 6),\\ \frac{m-5}{6}\times 8+8=\frac{4m+4}{3},&m\equiv 5(\bmod\ 6).\\ \end{array}\right.}

Hence, we have

\gamma_{oiR}(P_{2}\Box C_{m})\leq\left\{\begin{array}[]{lllllllll}\lceil\frac{4m}{3}\rceil+1,&m\equiv 3,5(\bmod\ 6),\\ \lceil\frac{4m}{3}\rceil,&otherwise.\end{array}\right.

(2) $\gamma_{oiR}(P_{2}\Box C_{m})\geq\lceil\frac{4m}{3}\rceil+1$ for $m\equiv 3,5(\bmod\ 6)$ , $\gamma_{oiR}(P_{2}\Box C_{m})\geq\lceil\frac{4m}{3}\rceil$ otherwise.

Let $f$ be a $\gamma_{oiR}$ -function of $P_{2}\Box C_{m}$ . Denote $V^{j}=\{v_{0,j},v_{1,j}\}(0\leq j\leq m-1)$ , $f^{j}=f(V^{j})=f(v_{0,j})+f(v_{1,j})$ . By the definition of OIRDF, $f^{j}\geq 1$ and if $f^{j}=1$ , then $f^{j-1}\geq 2$ or $f^{j+1}\geq 2$ . Then we use the following algorithm to group $V^{j}$ ( $0\leq j\leq m-1$ ) into three categories.

Input:

V^{j}

Output:

t_{0},t_{1},t_{2},B^{0}_{t_{0}},B^{1}_{t_{1}},B^{2}_{t_{2}}

Initialize $t_{0}=t_{1}=t_{2}=0$ , $B^{0}_{t_{0}}=B^{1}_{t_{1}}=B^{2}_{t_{2}}=\emptyset$ and $d^{j}=0$ for $j=0$ up to $m-1$ ;

for $j$ from $0$ to $m-1$ with $f^{j}\geq 3\wedge d^{j}=0$ do

t_{2}=t_{2}+1

d^{j}=1

B^{2}_{t_{2}}=\{V^{j}\}

;

if $f^{j-1}=1\wedge d^{j-1}=0$ then

d^{j-1}=1

B^{2}_{t_{2}}=B^{2}_{t_{2}}\cup\{V^{j-1}\}

;

end if

if $f^{j+1}=1\wedge d^{j+1}=0$ then

d^{j+1}=1

B^{2}_{t_{2}}=B^{2}_{t_{2}}\cup\{V^{j+1}\}

;

end if

Note:\sum_{V^{j}\in B^{2}_{t_{2}}}f^{j}>\frac{4}{3}|B^{2}_{t_{2}}|+\frac{2}{3}

end for

for $j$ from $0$ to $m-1$ with $f^{j}=2\wedge d^{j}=0$ do

if $f^{j-1}=f^{j+1}=1\wedge d^{j-1}=d^{j+1}=0$ then

t_{0}=t_{0}+1

d^{j-1}=d^{j}=d^{j+1}=1

B^{0}_{t_{0}}=\{V^{j-1},V^{j},V^{j+1}\}

;

Note:\sum_{V^{j}\in B^{0}_{t_{0}}}f^{j}=4=\frac{4}{3}|B^{0}_{t_{0}}|

end if

else if $f^{j-1}=1\wedge d^{j-1}=0$ then

t_{1}=t_{1}+1

d^{j-1}=d^{j}=1

B^{1}_{t_{1}}=\{V^{j-1},V^{j}\}

;

Note:\sum_{V^{j}\in B^{1}_{t_{1}}}f^{j}=3=\frac{4}{3}|B^{1}_{t_{1}}|+\frac{1}{3}

end if

else if $f^{j+1}=1\wedge d^{j+1}=0$ then

t_{1}=t_{1}+1

d^{j}=d^{j+1}=1

B^{1}_{t_{1}}=\{V^{j},V^{j+1}\}

;

Note:\sum_{V^{j}\in B^{1}_{t_{1}}}f^{j}=3=\frac{4}{3}|B^{1}_{t_{1}}|+\frac{1}{3}

end if

else

t_{2}=t_{2}+1

d^{j}=1

B^{2}_{t_{2}}=\{V^{j}\}

;

Note:\sum_{V^{j}\in B^{2}_{t_{2}}}f^{j}=2=\frac{4}{3}|B^{2}_{t_{2}}|+\frac{2}{3}

end if

end for

Algorithm 1 Dividing groups

V^{j}

(

0\leq j\leq m-1,j\in N

) into three categories

By Algorithm 1,

\begin{split}w(f)&=\sum\limits_{j=0}^{m-1}f^{j}\\ &=\sum\limits_{t=1}^{t_{0}}\sum_{V^{j}\in B^{0}_{t}}f^{j}+\sum\limits_{t=1}^{t_{1}}\sum_{V^{j}\in B^{1}_{t}}f^{j}+\sum\limits_{t=1}^{t_{2}}\sum_{V^{j}\in B^{2}_{t}}f^{j}\\ &\geq\sum\limits_{t=1}^{t_{0}}\frac{4}{3}|B^{0}_{t}|+\sum\limits_{t=1}^{t_{1}}(\frac{4}{3}|B^{1}_{t}|+\frac{1}{3})+\sum\limits_{t=1}^{t_{2}}(\frac{4}{3}|B^{2}_{t}|+\frac{2}{3})\\ &=\frac{4m}{3}+\frac{t_{1}}{3}+\frac{2t_{2}}{3}.\end{split}

Hence, $w(f)\geq\lceil\frac{4m}{3}\rceil$ . Then $\gamma_{oiR}(P_{2}\Box C_{m})\geq\lceil\frac{4m}{3}\rceil$ for $m\not\equiv 3,5(\bmod\ 6)$ . Next, we will prove $\gamma_{oiR}(P_{2}\Box C_{m})\geq\lceil\frac{4m}{3}\rceil+1$ for $m\equiv 3,5(\bmod\ 6)$ by contradiction.

Suppose $w(f)\leq\lceil\frac{4m}{3}\rceil$ for $m\equiv 3,5(\bmod\ 6)$ . For $m\equiv 3(\bmod\ 6)$ , $w(f)\leq\lceil\frac{4m}{3}\rceil=\frac{4m}{3}$ , then $t_{1}=t_{2}=0$ . For $m\equiv 5(\bmod\ 6)$ , $w(f)\leq\lceil\frac{4m}{3}\rceil=\frac{4m}{3}+\frac{1}{3}$ , then $t_{1}\leq 1$ , $t_{2}=0$ . By Algorithm 1, we know the details on $B^{k}_{t}$ ( $0\leq k\leq 1$ , $0\leq t\leq t_{k}$ ).

$B^{0}_{t}=\{V^{j-1},V^{j},V^{j+1}\}$ ( $0\leq t\leq t_{0}$ ) where $f(V^{j})=2$ and $f(V^{j-1})=f(V^{j+1})=1$ , then we denote $f(B^{0}_{t})=(1,2,1)$ , and the corresponding segments of $f$ are as follows.

\small{\begin{array}[]{ccccccccccccccccc}S_{0,1}=\left(\begin{array}[]{ccccccc}010\\ 111\end{array}\right),S_{0,2}=\left(\begin{array}[]{ccccccc}111\\ 010\end{array}\right),S_{0,3}=\left(\begin{array}[]{ccccccc}110\\ 011\end{array}\right),\\ S_{0,4}=\left(\begin{array}[]{ccccccc}011\\ 110\end{array}\right),S_{0,5}=\left(\begin{array}[]{ccccccc}020\\ 101\end{array}\right),S_{0,6}=\left(\begin{array}[]{ccccccc}101\\ 020\end{array}\right).\end{array}}

$B^{1}_{t}=\{V^{j-1},V^{j}\}$ or $\{V^{j},V^{j+1}\}$ ( $0\leq t\leq t_{1}$ ) where $f(V^{j})=2$ and $f(V^{j-1})=f(V^{j+1})=1$ , then $f(B^{1}_{t})=(1,2)$ or $(2,1)$ , and the corresponding segments of $f$ are as follows.

\small{\begin{array}[]{ccccccccccccccccc}S_{1,1}=\left(\begin{array}[]{ccccccc}01\\ 11\end{array}\right),S_{1,2}=\left(\begin{array}[]{ccccccc}11\\ 01\end{array}\right),S_{1,3}=\left(\begin{array}[]{ccccccc}02\\ 10\end{array}\right),S_{1,4}=\left(\begin{array}[]{ccccccc}10\\ 02\end{array}\right),\\ S_{1,5}=\left(\begin{array}[]{ccccccc}10\\ 11\end{array}\right),S_{1,6}=\left(\begin{array}[]{ccccccc}11\\ 10\end{array}\right),S_{1,7}=\left(\begin{array}[]{ccccccc}20\\ 01\end{array}\right),S_{1,8}=\left(\begin{array}[]{ccccccc}01\\ 20\end{array}\right).\end{array}}

For $m\equiv 3(\bmod\ 6)$ , $t_{1}=t_{2}=0$ . Then $f$ only has $S_{0,i}$ ( $1\leq i\leq 6$ ). In fact, $f$ only has $S_{0,5}$ and $S_{0,6}$ . If $f$ contains $S_{0,1}$ , then

\small{f(V)=\left(\begin{array}[]{ccccccc}\cdots&f(v)&010&f(u)&\cdots\\ \cdots&&111&&\cdots\end{array}\right)}

where $f(v)=f(u)=2$ . It has $S_{0,1}$ cannot be placed before or after $S_{0,i}$ ( $1\leq i\leq 6$ ). Thus, $f$ cannot contains $S_{0,1}$ . Similarly, $f$ can not contains $S_{0,i}$ ( $2\leq i\leq 4$ ). Since $f$ is an OIRDF, it cannot consist of only $S_{0,5}$ or only $S_{0,6}$ . Then it must be

\small{f(V)=\left(\begin{array}[]{cc:c:cc:cc}020&101&\cdots&020&101&020&101\\ 101&020&\cdots&101&020&101&020\end{array}\right).}

It has $m\equiv 0(\bmod\ 6)$ which contradicts to $m\equiv 3(\bmod\ 6)$ .

For $m\equiv 5(\bmod\ 6)$ , $t_{1}\leq 1$ , $t_{2}=0$ . If $t_{1}=0$ , then $m\equiv 0(\bmod\ 6)$ , thus $t_{1}=1$ for $m\equiv 5(\bmod\ 6)$ . That is, $f$ contains only one $S_{1,i}$ $(1\leq i\leq 8)$ . Since $f$ is an OIRDF, it cannot contain $S_{1,1}$ , $S_{1,2}$ , $S_{1,5}$ and $S_{1,6}$ . Then it must be

\begin{array}[]{lllllllllll}f(V)=\small{\left(\begin{array}[]{cc:c:ccc:c:cc}020&101&\cdots&020&10&101&\cdots&020&101\\ 101&020&\cdots&101&02&020&\cdots&101&020\end{array}\right)}\mbox{ or }\\ f(V)=\small{\left(\begin{array}[]{cc:c:ccc:c:cc}020&101&\cdots&020&20&101&\cdots&020&101\\ 101&020&\cdots&101&01&020&\cdots&101&020\end{array}\right)}\mbox{ or }\\ f(V)=\small{\left(\begin{array}[]{cc:c:ccc:c:cc}101&020&\cdots&101&02&020&\cdots&101&020\\ 020&101&\cdots&020&10&101&\cdots&020&101\end{array}\right)}\mbox{ or }\\ f(V)=\small{\left(\begin{array}[]{cc:c:ccc:c:cc}101&020&\cdots&101&01&020&\cdots&101&020\\ 020&101&\cdots&020&20&101&\cdots&020&101\end{array}\right)}\end{array}

It has $m\equiv 2(\bmod\ 6)$ which contradicts to $m\equiv 5(\bmod\ 6)$ .

Therefore, $\gamma_{oiR}(P_{2}\Box C_{m})=w(f)\geq\lceil\frac{4m}{3}\rceil+1$ for $m\equiv 3,5(\bmod\ 6)$ .

Theorem 2.5

For any integer $m\geq 3$ ,

\gamma_{oiR}(P_{3}\Box C_{m})=\left\{\begin{array}[]{lllllllll}2m,&m\equiv 0(\bmod\ 2),\\ 2m+1,&m\equiv 1(\bmod\ 2).\end{array}\right.

Proof 2.6

Let $G=P_{3}\Box C_{m}$ , $V(G)=\{v_{i,j}|0\leq i\leq 2,0\leq j\leq m-1\}$ .

(1) $2m$ and $2m+1$ are the upper bounds of $\gamma_{oiR}(P_{3}\Box C_{m})$ for $m\equiv 0(\bmod\ 2)$ and $m\equiv 1(\bmod\ 2)$ respectively. We first define a function $h$ on $\{v_{i,j}|0\leq i\leq 2,0\leq j\leq 1\}$ .

\displaystyle\small{h(v_{i,j})=\left\{\begin{array}[]{llllll}2,&i=1,j=0,\\ 1,&i=0,2,j=1,\\ 0,&otherwise.\end{array}\right.\text{\ \ i.e.\ \ }h=\left(\begin{array}[]{llllll}01\\ 20\\ 01\end{array}\right).}

Then we define an OIRDF $f$ on $P_{3}\Box C_{m}$ as follows,

\small{f(v_{i,j})=\left\{\begin{array}[]{llllll}1,&m\equiv 1(\bmod\ 2),j=m-1,\\ h(v_{i,j\bmod\ 2}),&otherwise.\end{array}\right.}

That is,

\displaystyle\small{\begin{array}[]{llllllllll}m\equiv 0(\bmod\ 2),&&&&&&m\equiv 1(\bmod\ 2),\\ f=\left(\begin{array}[]{ccccccccccc}01&\cdots&01\\ 20&\cdots&20\\ 01&\cdots&01\end{array}\right),&&&&&&f=\left(\begin{array}[]{cccccc}01&\cdots&01&1\\ 20&\cdots&20&1\\ 01&\cdots&01&1\end{array}\right).\end{array}}

One can check $f$ is an OIRDF and the weight is $w(f)=4\times\frac{m}{2}=2m$ for $m\equiv 0(\bmod\ 2)$ and $w(f)=4\times\frac{m-1}{2}+3=2m+1$ for $m\equiv 1(\bmod\ 2)$ .

Hence, $\gamma_{oiR}(P_{3}\Box C_{m})\leq 2m$ for $m\equiv 0(\bmod\ 2)$ and $\gamma_{oiR}(P_{3}\Box C_{m})\leq 2m+1$ for $m\equiv 1(\bmod\ 2)$ .

(2) $2m$ and $2m+1$ are the lower bounds of $\gamma_{oiR}(P_{3}\Box C_{m})$ for $m\equiv 0(\bmod\ 2)$ and $m\equiv 1(\bmod\ 2)$ respectively.

We can find a $\gamma_{oiR}$ -function $f$ satisfying properties (a) and (b). Denote $V^{j}=\{v_{i,j}\mid 0\leq i\leq 2\}(0\leq j\leq m-1)$ , $f^{j}=f(V^{j})=\sum_{v_{i,j}\in V^{j}}f(v_{i,j})$ .

(a) For $0\leq j\leq m-1$ , $f^{j}\geq 1$ ; if $f^{j}=1$ , then $f^{j+1}\geq 2$ and $f^{j-1}+f^{j+1}\geq 6$ .

(b) If $f^{j-1}=f^{j+1}=1$ , then $2\leq f^{j}\leq 3$ .

In which superscripts are taken modulo $m$ .

For (a), since $V_{0}$ is independent, then $f^{j}\neq 0$ , i.e. $f^{j}\geq 1$ . Furthermore, if $f^{j}=1$ , then $f(v_{0,j})=f(v_{2,j})=0$ , $f(v_{1,j})=1$ , and $f(v_{0,j+1})\geq 1$ and $f(v_{2,j+1})\geq 1$ , it follows $f^{j+1}\geq 2\neq 1$ . Additionally, since for each $u\in V_{0}$ , there exists at least one vertex $v\in N(u)$ with $f(v)=2$ , then $f(v_{0,j-1})+f(v_{0,j+1})\geq 3$ , $f(v_{2,j-1})+f(v_{2,j+1})\geq 3$ , it follows $f^{j-1}+f^{j+1}\geq 6$ .

For (b), if $f^{j-1}=f^{j+1}=1$ , by (a), $f^{j}\neq 1$ . Suppose $f^{j}\geq 4$ . Since $V_{0}$ is independent and $f^{j-1}=f^{j+1}=1$ , then $f(v_{0,j-1})=f(v_{2,j-1})=f(v_{0,j+1})=f(v_{2,j+1})=0$ , $f(v_{1,j-1})=f(v_{1,j+1})=1$ . Define an OIRDF $f^{\prime}$ as: $f^{\prime}(v_{0,j-1})=f^{\prime}(v_{2,j-1})=f^{\prime}(v_{1,j})=f^{\prime}(v_{0,j+1})=f^{\prime}(v_{2,j+1})=0$ , $f^{\prime}(v_{0,j})=f^{\prime}(v_{2,j})=1$ , $f^{\prime}(v_{1,j-1})=f^{\prime}(v_{1,j+1})=2$ . Then $w(f^{\prime})\leq w(f)$ . If $w(f^{\prime})<w(f)$ , then there is contradiction to $f$ being a $\gamma_{oiR}$ -function. If $w(f^{\prime})=w(f)$ , then we find a $\gamma_{oiR}$ -function $f^{\prime}$ with $f^{\prime}_{j-1}=f^{\prime}_{j+1}=1$ and $2\leq f^{\prime}_{j}\leq 3$ .

Then we use Algorithm 2 to group $V^{j}$ ( $0\leq j\leq m-1$ ) into two categories.

Input:

V^{j}

Output:

t_{0},t_{1},B^{0}_{t_{0}},B^{1}_{t_{1}}

Initialize $t_{0}=t_{1}=0$ , $B^{0}_{t_{0}}=B^{1}_{t_{1}}=\emptyset$ and $d^{j}=0$ for $j=0$ up to $m-1$ ;

for $j$ from 0 to $m-1$ with $f^{j}\geq 4\wedge d^{j}=0$ do

t_{1}=t_{1}+1

d^{j}=1

B^{1}_{t_{1}}=\{V^{j}\}

;

if $f^{j-1}=1\wedge d^{j-1}=0$ then

d^{j-1}=1

B^{1}_{t_{1}}=B^{1}_{t_{1}}\cup\{V^{j-1}\}

;

end if

if $f^{j+1}=1\wedge d^{j+1}=0$ then

d^{j+1}=1

B^{1}_{t_{1}}=B^{1}_{t_{1}}\cup\{V^{j+1}\}

;

end if

Note:\sum_{V^{j}\in B^{1}_{t_{1}}}f^{j}\geq 2|B^{1}_{t_{1}}|+1

end for

for $j$ from 0 to $m-1$ with $f^{j}=3\wedge d^{j}=0$ do

if $f^{j+1}=1\wedge d^{j+1}=0$ then

t_{0}=t_{0}+1

d^{j}=d^{j+1}=1

B^{0}_{t_{0}}=\{V^{j},V^{j+1}\}

;

Note:\sum_{V^{j}\in B^{0}_{t_{0}}}f^{j}=4=2|B^{0}_{t_{0}}|

end if

else

t_{1}=t_{1}+1

d^{j}=1

B^{1}_{t_{1}}=\{V^{j}\}

;

Note:\sum_{V^{j}\in B^{1}_{t_{1}}}f^{j}=3=2|B^{1}_{t_{1}}|+1

end if

end for

for $j$ from 0 to $m-1$ with $f^{j}=2\wedge d^{j}=0$ do

t_{0}=t_{0}+1

d^{j}=1

B^{0}_{t_{0}}=\{V^{j}\}

;

Note:\sum_{V^{j}\in B^{0}_{t_{0}}}f^{j}=2=2|B^{0}_{t_{0}}|

end for

Algorithm 2 Dividing groups

V^{j}

(

0\leq j\leq m-1,j\in N

) into two categories

By Algorithm 2,

\begin{split}w(f)&=\sum\limits_{j=0}^{m-1}f^{j}=\sum\limits_{t=1}^{t_{0}}\sum_{V^{j}\in B^{0}_{t}}f^{j}+\sum\limits_{t=1}^{t_{1}}\sum_{V^{j}\in B^{1}_{t}}f^{j}\geq\sum\limits_{t=1}^{t_{0}}(2|B^{0}_{t}|)+\sum\limits_{t=1}^{t_{1}}(2|B^{1}_{t}|+1)=2m+t_{1}.\end{split}

Hence, $w(f)\geq 2m$ . Then $\gamma_{oiR}(P_{3}\Box C_{m})\geq 2m$ for $m\equiv 0(\bmod\ 2)$ . Next, we will prove $\gamma_{oiR}(P_{3}\Box C_{m})\geq 2m+1$ for $m\equiv 1(\bmod\ 2)$ by contradiction.

Suppose $w(f)\leq 2m$ for $m\equiv 1(\bmod\ 2)$ , then $t_{1}=0$ . By Algorithm 2, we know the details on $B^{0}_{t}$ ( $0\leq t\leq t_{0}$ ).

$B^{0}_{t}=\{V^{j},V^{j+1}\}$ where $f(V^{j})=3$ and $f(V^{j+1})=1$ , then $f(B^{0}_{t})=(3,1)$ . Or $B^{0}_{t}=\{V^{j}\}$ where $f(V^{j})=2$ , then $f(B^{0}_{t})=(2)$ . The corresponding segments of $f$ are as follows.

\small{\begin{array}[]{lllllllllccccccccc}&S_{0,1}=\left(\begin{array}[]{ccccccc}10\\ 11\\ 10\end{array}\right),&S_{0,2}=\left(\begin{array}[]{ccccccc}10\\ 01\\ 20\end{array}\right),&S_{0,3}=\left(\begin{array}[]{ccccccc}20\\ 01\\ 10\end{array}\right),\\ &S_{0,4}=\left(\begin{array}[]{ccccccc}0\\ 1\\ 1\end{array}\right),&S_{0,5}=\left(\begin{array}[]{ccccccc}1\\ 1\\ 0\end{array}\right),&S_{0,6}=\left(\begin{array}[]{ccccccc}1\\ 0\\ 1\end{array}\right),&S_{0,7}=\left(\begin{array}[]{ccccccc}0\\ 2\\ 0\end{array}\right).\end{array}}

Since $t_{1}=0$ , then $f$ only contains $S_{0,i}$ $(1\leq i\leq 7)$ . However, $f$ does not contain $S_{0,1}$ . If not, then

\small{f(V)=\left(\begin{array}[]{ccccccc}\cdots&10&f(u)&\cdots\\ \cdots&11&&\cdots\\ \cdots&10&f(v)&\cdots\end{array}\right)}

where $f(u)=f(v)=2$ . It has $S_{0,1}$ cannot be placed before $S_{0,i}$ ( $1\leq i\leq 7$ ). Therefore, $f$ does not contain $S_{0,1}$ .

$f$ does not contain $S_{0,2}$ and $S_{0,3}$ , otherwise $f$ must be

\small{f(V)=\left(\begin{array}[]{ccccccc}10&20&\cdots&10&20\\ 01&01&\cdots&01&01\\ 20&10&\cdots&20&10\end{array}\right)}.

It has $m\equiv 0(\bmod\ 2)$ which contradicts to $m\equiv 1(\bmod\ 2)$ .

$f$ does not contain $S_{0,4}$ and $S_{0,5}$ . If $f$ contains $S_{0,4}$ , then

\small{f(V)=\left(\begin{array}[]{ccccccc}\cdots&f(u)&0&f(v)&\cdots\\ \cdots&&1&&\cdots\\ \cdots&&1&&\cdots\end{array}\right)}

where $f(u)=2$ or $f(v)=2$ . It follows $S_{0,4}$ cannot be placed before or after $S_{0,i}$ ( $4\leq i\leq 7$ ). Since $f$ does not contain $S_{0,i}$ ( $i=1,2,3$ ), then $f$ does not contain $S_{0,4}$ . Similarly, $f$ does not contain $S_{0,5}$ .

Then $f$ consists of $S_{0,6}$ and $S_{0,7}$ . Since $f$ is an OIRDF, then $f$ must be

\small{f(V)=\left(\begin{array}[]{ccccccc}10&10&\cdots&10&10\\ 02&02&\cdots&02&02\\ 10&10&\cdots&10&10\end{array}\right)}.

It has $m\equiv 0(\bmod\ 2)$ which contradicts to $m\equiv 1(\bmod\ 2)$ .

Therefore, $\gamma_{oiR}(P_{3}\Box C_{m})=w(f)\geq 2m+1$ for $m\equiv 1(\bmod\ 2)$ .

3 The outer independent Roman domination number of $P_{n}\Box C_{3}$

Theorem 3.1

For any integer $n\geq 3$ , $\gamma_{oiR}(P_{n}\Box C_{3})=\lceil\frac{7n}{3}\rceil$ .

Proof 3.2

Let $G=P_{n}\Box C_{3}$ , $V(G)=\{v_{i,j}|0\leq i\leq n-1,0\leq j\leq 2\}$ .

(1) $\lceil\frac{7n}{3}\rceil$ is the upper bound of $\gamma_{oiR}(P_{n}\Box C_{3})$ . We first define a function $h$ on $P_{6}\Box C_{3}$ .

\small{h(v_{i,j})=\left\{\begin{array}[]{llllll}2,&(i=1,j=0)\vee(i=4,j=1),\\ 1,&(i=3,5,j=0)\vee(i=0,2,j=1)\vee j=2,\\ 0,&otherwise.\end{array}\right.\text{\ \ i.e.\ \ }h=\left(\begin{array}[]{llllll}011\\ 201\\ 011\\ 101\\ 021\\ 101\end{array}\right).}

Then we define an OIRDF $f$ on $P_{3}\Box C_{m}$ as follows.

\small{f(v_{i,j})=\left\{\begin{array}[]{llllll}2,&n\equiv 1,4(\bmod\ 6),i=n-1,j=2,\\ h(v_{i\bmod 6,j}),&otherwise.\end{array}\right.}

That is,

\displaystyle\small{\left(\begin{array}[]{cc}011\\ 201\\ 011\\ 101\\ 021\\ 101\\ \vdots\\ 011\\ 201\\ 011\\ 101\\ 021\\ 101\\ \end{array}\right),\left(\begin{array}[]{cc}011\\ 201\\ 011\\ 101\\ 021\\ 101\\ \vdots\\ 011\\ 201\\ 011\\ 101\\ 021\\ 101\\ \\ 012\end{array}\right),\left(\begin{array}[]{cc}011\\ 201\\ 011\\ 101\\ 021\\ 101\\ \vdots\\ 011\\ 201\\ 011\\ 101\\ 021\\ 101\\ \\ 011\\ 201\\ \end{array}\right),\left(\begin{array}[]{cc}011\\ 201\\ 011\\ 101\\ 021\\ 101\\ \vdots\\ 011\\ 201\\ 011\\ 101\\ 021\\ 101\\ \\ 011\\ 201\\ 011\\ \end{array}\right),\left(\begin{array}[]{cc}011\\ 201\\ 011\\ 101\\ 021\\ 101\\ \vdots\\ 011\\ 201\\ 011\\ 101\\ 021\\ 101\\ \\ 011\\ 201\\ 011\\ 102\\ \end{array}\right),\left(\begin{array}[]{cc}011\\ 201\\ 011\\ 101\\ 021\\ 101\\ \vdots\\ 011\\ 201\\ 011\\ 101\\ 021\\ 101\\ \\ 011\\ 201\\ 011\\ 101\\ 021\\ \end{array}\right).}

One can check that $f$ is an OIRDF and the weight is

\small{w(f)=\left\{\begin{array}[]{lllllllll}\frac{n}{6}\times 14=\frac{7n}{3},&n\equiv 0(\bmod 6),\\ \frac{n-1}{6}\times 14+3=\frac{7n+2}{3},&n\equiv 1(\bmod 6),\\ \frac{n-2}{6}\times 14+5=\frac{7n+1}{3},&n\equiv 2(\bmod 6),\\ \frac{n-3}{6}\times 14+7=\frac{7n}{3},&n\equiv 3(\bmod 6),\\ \frac{n-4}{6}\times 14+10=\frac{7n+2}{3},&n\equiv 4(\bmod 6),\\ \frac{n-5}{6}\times 14+12=\frac{7n+1}{3},&n\equiv 5(\bmod 6).\end{array}\right.}

Hence, $\gamma_{oiR}(P_{n}\Box C_{3})\leq\lceil\frac{7n}{3}\rceil$ .

(2) $\lceil\frac{7n}{3}\rceil$ is the lower bound of $\gamma_{oiR}(P_{n}\Box C_{3})$ . Let $f$ be a $\gamma_{oiR}$ -function of $P_{n}\Box C_{3}$ . Denote $V^{i}=\{v_{i,j}\mid 0\leq j\leq 2\}(0\leq i\leq n-1)$ , $f^{i}=f(V^{i})=\sum_{v_{i,j}\in V^{i}}f(v_{i,j})$ . Then $f$ has properties (a) and (b).

(a) $f^{i-1}+f^{i}+f^{i+1}\geq 7$ for every integer $i$ $(1\leq i\leq n-2)$ where superscripts are taken modulo $n$ .

Since $V_{0}$ is independent, we have $f^{i}\geq 2$ for every $i$ $(0\leq i\leq n-1)$ . For some $i$ $(1\leq i\leq n-2)$ , if $f^{i}\geq 3$ , then $f^{i-1}+f^{i}+f^{i+1}\geq 7$ ; if $f^{i}=2$ , without loss of generality, let $f(v_{i,0})=0$ , $f(v_{i,1})=f(v_{i,2})=1$ , then $f(v_{i-1,0})+f(v_{i+1,0})\geq 3$ , $f(v_{i-1,1})+f(v_{i-1,2})\geq 1$ , $f(v_{i+1,1})+f(v_{i+1,2})\geq 1$ , it follows $f^{i-1}+f^{i}+f^{i+1}\geq 7$ .

(b) $f^{0}+f^{1}\geq 5$ and $f^{n-1}+f^{n-2}\geq 5$ .

Since $f^{i}\geq 2$ for every $i$ $(0\leq i\leq n-1)$ , if $f^{0}\geq 3$ , then $f^{0}+f^{1}\geq 5$ ; if $f^{0}=2$ , without loss of generality, let $f(v_{0,0})=0$ , $f(v_{0,1})=f(v_{0,2})=1$ , then $f(v_{1,0})=2$ , $f(v_{1,1})+f(v_{1,2})\geq 1$ , i.e. $f^{1}\geq 3$ , it follows $f^{0}+f^{1}\geq 5$ . Similarly, $f^{n-1}+f^{n-2}\geq 5$ .

By (a) and (b), we have

\small{\begin{split}3w(f)&=\sum_{i=0}^{n-3}(f^{i}+f^{i+1}+f^{i+2})+2f^{0}+2f^{n-1}+f^{1}+f^{n-2}\\ &=\sum_{i=0}^{n-3}(f^{i}+f^{i+1}+f^{i+2})+(f^{0}+f^{1})+f^{0}+(f^{n-2}+f^{n-1})+f^{n-1}\\ &\geq 7(n-2)+5+2+5+2=7n.\end{split}}

Therefore, $\gamma_{oiR}(P_{n}\Box C_{3})\geq\lceil\frac{7n}{3}\rceil$ .

4 Upper bounds on the outer independent Roman domination number of $P_{n}\Box C_{m}$ , $n,m\geq 4$

Theorem 4.1

For any integers $m,n\geq 4$ , $\gamma_{oiR}(P_{n}\Box C_{m})\leq\frac{5mn+5n+2m}{8}$ .

Proof 4.2

Let $G=P_{n}\Box C_{m}$ , $V(G)=\{v_{i,j}|0\leq i\leq n-1,0\leq j\leq m-1\}$ . We first define a function $g$ on $P_{4}\Box C_{4}$ as follows.

\displaystyle\small{g(v_{i,j})=\left\{\begin{array}[]{llllll}2,&(i=0,j=2)\vee(i=2,j=0),\\ 1,&(i=0,j=0)\vee(i=1,3,j=1,3)\vee(i=2,j=2),\\ 0,&otherwise.\end{array}\right.\text{\ \ i.e.\ \ }g=\left(\begin{array}[]{llllll}1020\\ 0101\\ 2010\\ 0101\end{array}\right).}

(1) For $m\equiv 0(\bmod 4)$ , we define an OIRDF $f$ on $P_{n}\Box C_{m}$ as the following.

\small{f(v_{i,j})=\left\{\begin{array}[]{llllll}2,&n\equiv 0,2(\bmod\ 4),i=n-1,j\equiv 3(\bmod\ 4),\\ g(v_{i\bmod 4,j\bmod 4}),&otherwise.\end{array}\right.}

Also, we can write $f$ as the following.

\displaystyle\small{\begin{array}[]{llllllllllll}n\equiv 1(\bmod\ 4),&&&n\equiv 2(\bmod\ 4),\\ f=\left(\begin{array}[]{ccccccccccc}1020&\cdots&1020\\ 0101&\cdots&0101\\ 2010&\cdots&2010\\ 0101&\cdots&0101\\ \vdots&\ddots&\vdots\\ 1020&\cdots&1020\\ 0101&\cdots&0101\\ 2010&\cdots&2010\\ 0101&\cdots&0101\\ \hdashline 1020&\cdots&1020\\ \end{array}\right),&&&f=\left(\begin{array}[]{cccccc}1020&\cdots&1020\\ 0101&\cdots&0101\\ 2010&\cdots&2010\\ 0101&\cdots&0101\\ \vdots&\ddots&\vdots\\ 1020&\cdots&1020\\ 0101&\cdots&0101\\ 2010&\cdots&2010\\ 0101&\cdots&0101\\ \hdashline 1020&\cdots&1020\\ 0102&\cdots&0102\end{array}\right),\end{array}}

\displaystyle\small{\begin{array}[]{llllllllll}n\equiv 3(\bmod\ 4),&&&n\equiv 0(\bmod\ 4),\\ f=\left(\begin{array}[]{ccccccc}1020&\cdots&1020\\ 0101&\cdots&0101\\ 2010&\cdots&2010\\ 0101&\cdots&0101\\ \vdots&\ddots&\vdots\\ 1020&\cdots&1020\\ 0101&\cdots&0101\\ 2010&\cdots&2010\\ 0101&\cdots&0101\\ \hdashline 1020&\cdots&1020\\ 0101&\cdots&0101\\ 2010&\cdots&2010\end{array}\right),&&&f=\left(\begin{array}[]{cccccc}1020&\cdots&1020\\ 0101&\cdots&0101\\ 2010&\cdots&2010\\ 0101&\cdots&0101\\ \vdots&\ddots&\vdots\\ 1020&\cdots&1020\\ 0101&\cdots&0101\\ 2010&\cdots&2010\\ 0101&\cdots&0101\\ \hdashline 1020&\cdots&1020\\ 0101&\cdots&0101\\ 2010&\cdots&2010\\ 0102&\cdots&0102\\ \end{array}\right).\end{array}}

Then the weight is

\small{w(f)=\left\{\begin{array}[]{lllllllll}\frac{m}{4}\times\frac{n-4}{4}\times 10+\frac{m}{4}\times 11=\frac{5mn+2m}{8},&n\equiv 0(\bmod\ 4),\\ \frac{m}{4}\times\frac{n-1}{4}\times 10+\frac{m}{4}\times 3=\frac{5mn+m}{8},&n\equiv 1(\bmod\ 4),\\ \frac{m}{4}\times\frac{n-2}{4}\times 10+\frac{m}{4}\times 6=\frac{5mn+2m}{8},&n\equiv 2(\bmod\ 4),\\ \frac{m}{4}\times\frac{n-3}{4}\times 10+\frac{m}{4}\times 8=\frac{5mn+m}{8},&n\equiv 3(\bmod\ 4).\end{array}\right.}

Hence,

\gamma_{oiR}(P_{n}\Box C_{m})\leq\left\{\begin{array}[]{lllllllll}\frac{5mn+2m}{8},&n\equiv 0,2(\bmod 4),\\ \frac{5mn+m}{8},&n\equiv 1,3(\bmod 4).\end{array}\right.

(2) For $m\equiv 1(\bmod 4)$ , we define an OIRDF $f$ on $P_{n}\Box C_{m}$ as the following.

\small{f(v_{i,j})=\left\{\begin{array}[]{llllll}2,&n\equiv 0(\bmod\ 4),i=n-1,j\equiv 3(\bmod\ 4),\\ &n\equiv 2(\bmod\ 4),i=n-1,j\equiv 3(\bmod\ 4),0\leq j\leq m-5,\\ &n\equiv 2(\bmod\ 4),i=n-1,j=m-1,\\ 1,&i\equiv 2(\bmod\ 4),j=m-2,\\ &n\equiv 0,1,3(\bmod\ 4),i\equiv 1,3(\bmod\ 4),j=m-1,\\ &n\equiv 2(\bmod\ 4),i\equiv 1(\bmod\ 4),j=m-1,0\leq i\leq n-3,\\ &n\equiv 2(\bmod\ 4),i\equiv 3(\bmod\ 4),j=m-1,\\ 0,&i\equiv 2(\bmod\ 4),j=m-1,\\ g(v_{i\bmod 4,j\bmod 4}),&otherwise.\end{array}\right.}

Also, we can write $f$ as follows.

\displaystyle\small{\begin{array}[]{llllllllll}n\equiv 1(\bmod\ 4),&&&n\equiv 2(\bmod\ 4),\\ f=\left(\begin{array}[]{cccccccc}1020&\cdots&1020&10201\\ 0101&\cdots&0101&01011\\ 2010&\cdots&2010&20110\\ 0101&\cdots&0101&01011\\ \vdots&\ddots&\vdots&\vdots\\ 1020&\cdots&1020&10201\\ 0101&\cdots&0101&01011\\ 2010&\cdots&2010&20110\\ 0101&\cdots&0101&01011\\ \hdashline 1020&\cdots&1020&10201\\ \end{array}\right),&&&f=\left(\begin{array}[]{cccccc}1020&\cdots&1020&10201\\ 0101&\cdots&0101&01011\\ 2010&\cdots&2010&20110\\ 0101&\cdots&0101&01011\\ \vdots&\ddots&\vdots&\vdots\\ 1020&\cdots&1020&10201\\ 0101&\cdots&0101&01011\\ 2010&\cdots&2010&20110\\ 0101&\cdots&0101&01011\\ \hdashline 1020&\cdots&1020&10201\\ 0102&\cdots&0102&01012\\ \end{array}\right),\end{array}}

\displaystyle\small{\begin{array}[]{lllllllllll}n\equiv 3(\bmod\ 4),&&&n\equiv 0(\bmod\ 4),\\ f=\left(\begin{array}[]{cccccccc}1020&\cdots&1020&10201\\ 0101&\cdots&0101&01011\\ 2010&\cdots&2010&20110\\ 0101&\cdots&0101&01011\\ \vdots&\ddots&\vdots&\vdots\\ 1020&\cdots&1020&10201\\ 0101&\cdots&0101&01011\\ 2010&\cdots&2010&20110\\ 0101&\cdots&0101&01011\\ \hdashline 1020&\cdots&1020&10201\\ 0101&\cdots&0101&01011\\ 2010&\cdots&2010&20110\\ \end{array}\right),&&&\ f=\left(\begin{array}[]{cccccc}1020&\cdots&1020&10201\\ 0101&\cdots&0101&01011\\ 2010&\cdots&2010&20110\\ 0101&\cdots&0101&01011\\ \vdots&\ddots&\vdots&\vdots\\ 1020&\cdots&1020&10201\\ 0101&\cdots&0101&01011\\ 2010&\cdots&2010&20110\\ 0101&\cdots&0101&01011\\ \hdashline 1020&\cdots&1020&10201\\ 0101&\cdots&0101&01011\\ 2010&\cdots&2010&20110\\ 0102&\cdots&0102&01021\\ \end{array}\right).\end{array}}

Then the weight is

\small{w(f)=\left\{\begin{array}[]{lllllllll}\frac{m-5}{4}\times\frac{n-4}{4}\times 10+\frac{n-4}{4}\times 14+\frac{m-5}{4}\times 11+15=\frac{5mn+3n+2m-2}{8},&n\equiv 0(\bmod\ 4),\\ \frac{m-5}{4}\times\frac{n-1}{4}\times 10+\frac{n-1}{4}\times 14+\frac{m-5}{4}\times 3+4=\frac{5mn+3n+m-1}{8},&n\equiv 1(\bmod\ 4),\\ \frac{m-5}{4}\times\frac{n-2}{4}\times 10+\frac{n-2}{4}\times 14+\frac{m-5}{4}\times 6+8=\frac{5mn+3n+2m-2}{8},&n\equiv 2(\bmod\ 4),\\ \frac{m-5}{4}\times\frac{n-3}{4}\times 10+\frac{n-3}{4}\times 14+\frac{m-5}{4}\times 8+11=\frac{5mn+3n+m-1}{8},&n\equiv 3(\bmod\ 4).\\ \end{array}\right.}

Hence,

\gamma_{oiR}(P_{n}\Box C_{m})\leq\left\{\begin{array}[]{lllllllll}\frac{5mn+3n+2m-2}{8},&n\equiv 0,2(\bmod 4),\\ \frac{5mn+3n+m-1}{8},&n\equiv 1,3(\bmod 4).\end{array}\right.

(3) For $m\equiv 2(\bmod 4)$ , we define an OIRDF $f$ on $P_{n}\Box C_{m}$ as the following.

\small{f(v_{i,j})=\left\{\begin{array}[]{llllll}2,&i\equiv 3(\bmod\ 4),j=m-3,\\ &i\equiv 1(\bmod\ 4),j=m-1,\\ &n\equiv 0(\bmod\ 4),i=n-1,j\equiv 3(\bmod\ 4),\\ &n\equiv 2(\bmod\ 4),i=n-1,j\equiv 3(\bmod\ 4),0\leq j\leq m-6,\\ 1,&n\equiv 0,1,2(\bmod\ 4),i\equiv 2(\bmod\ 4),j=m-2,\\ &n\equiv 3(\bmod\ 4),i\equiv 2(\bmod\ 4),j=m-2,0\leq i\leq n-4,\\ &n\equiv 1(\bmod\ 4),i=n-1,j=m-1,\\ g(v_{i\bmod 4,j\bmod 4}),&otherwise.\end{array}\right.}

Also, we can write $f$ as follows.

\displaystyle\small{\begin{array}[]{llllllllll}n\equiv 1(\bmod\ 4),&&&n\equiv 2(\bmod\ 4),\\ f=\left(\begin{array}[]{cccccccc}1020&\cdots&1020&102010\\ 0101&\cdots&0101&010102\\ 2010&\cdots&2010&201010\\ 0101&\cdots&0101&010201\\ \vdots&\ddots&\vdots&\vdots\\ 1020&\cdots&1020&102010\\ 0101&\cdots&0101&010102\\ 2010&\cdots&2010&201010\\ 0101&\cdots&0101&010201\\ \hdashline 1020&\cdots&1020&102011\\ \end{array}\right),&&&f=\left(\begin{array}[]{cccccc}1020&\cdots&1020&102010\\ 0101&\cdots&0101&010102\\ 2010&\cdots&2010&201010\\ 0101&\cdots&0101&010201\\ \vdots&\ddots&\vdots&\vdots\\ 1020&\cdots&1020&102010\\ 0101&\cdots&0101&010102\\ 2010&\cdots&2010&201010\\ 0101&\cdots&0101&010201\\ \hdashline 1020&\cdots&1020&102010\\ 0102&\cdots&0102&010102\\ \end{array}\right),\end{array}}

\displaystyle\small{\begin{array}[]{llllllllllll}n\equiv 3(\bmod\ 4),&&&n\equiv 0(\bmod\ 4),\\ f=\left(\begin{array}[]{cccccccc}1020&\cdots&1020&102010\\ 0101&\cdots&0101&010102\\ 2010&\cdots&2010&201010\\ 0101&\cdots&0101&010201\\ \vdots&\ddots&\vdots&\vdots\\ 1020&\cdots&1020&102010\\ 0101&\cdots&0101&010102\\ 2010&\cdots&2010&201010\\ 0101&\cdots&0101&010201\\ \hdashline 1020&\cdots&1020&102010\\ 0101&\cdots&0101&010102\\ 2010&\cdots&2010&201020\\ \end{array}\right),&&&f=\left(\begin{array}[]{cccccc}1020&\cdots&1020&102010\\ 0101&\cdots&0101&010102\\ 2010&\cdots&2010&201010\\ 0101&\cdots&0101&010201\\ \vdots&\ddots&\vdots&\vdots\\ 1020&\cdots&1020&102010\\ 0101&\cdots&0101&010102\\ 2010&\cdots&2010&201010\\ 0101&\cdots&0101&010201\\ \hdashline 1020&\cdots&1020&102010\\ 0101&\cdots&0101&010102\\ 2010&\cdots&2010&201010\\ 0102&\cdots&0102&010201\\ \end{array}\right).\end{array}}

Then the weight is

\small{w(f)=\left\{\begin{array}[]{lllllllll}\frac{m-6}{4}\times\frac{n-4}{4}\times 10+\frac{n-4}{4}\times 16+\frac{m-6}{4}\times 11+16=\frac{5mn+2n+2m-12}{8},&n\equiv 0(\bmod\ 4),\\ \frac{m-6}{4}\times\frac{n-1}{4}\times 10+\frac{n-1}{4}\times 16+\frac{m-6}{4}\times 3+5=\frac{5mn+2n+m+2}{8},&n\equiv 1(\bmod\ 4),\\ \frac{m-6}{4}\times\frac{n-2}{4}\times 10+\frac{n-2}{4}\times 16+\frac{m-6}{4}\times 6+8=\frac{5mn+2n+2m-12}{8},&n\equiv 2(\bmod\ 4),\\ \frac{m-6}{4}\times\frac{n-3}{4}\times 10+\frac{n-3}{4}\times 16+\frac{m-6}{4}\times 8+13=\frac{5mn+2n+m+2}{8},&n\equiv 3(\bmod\ 4).\\ \end{array}\right.}

Hence,

\small{\gamma_{oiR}(P_{n}\Box C_{m})\leq\left\{\begin{array}[]{lllllllll}\frac{5mn+2n+2m-12}{8},&n\equiv 0,2(\bmod 4),\\ \frac{5mn+2n+m+2}{8},&n\equiv 1,3(\bmod 4).\end{array}\right.}

(4) For $m\equiv 3(\bmod 4)$ , we define an OIRDF $f$ on $P_{n}\Box C_{m}$ as the following.

\small{f(v_{i,j})=\left\{\begin{array}[]{llllll}2,&i\equiv 1(\bmod\ 4),j=m-2,\\ &n\equiv 0(\bmod\ 4),i=n-1,j\equiv 3(\bmod\ 4),\\ 1,&i\equiv 3(\bmod\ 4),j=m-1,\\ &n\equiv 0,3(\bmod\ 4),i\equiv 0,1(\bmod\ 4),j=m-1,\\ &n\equiv 0(\bmod\ 4),i=n-2,j=m-3,\\ &n\equiv 1(\bmod\ 4),i\equiv 0(\bmod\ 4),j=m-1,0\leq i\leq n-5,\\ &n\equiv 1(\bmod\ 4),i\equiv 1(\bmod\ 4),j=m-1,\\ &n\equiv 2(\bmod\ 4),i\equiv 0(\bmod\ 4),j=m-1,\\ &n\equiv 2(\bmod\ 4),i\equiv 1(\bmod\ 4),j=m-1,0\leq i\leq n-5,\\ &n\equiv 2(\bmod\ 4),i=n-1,j\equiv 0(\bmod\ 4),0\leq j\leq m-7,\\ g(v_{i\bmod 4,j\bmod 4}),&otherwise.\end{array}\right.}

Also, we can write $f$ as follows.

\displaystyle\small{\begin{array}[]{lllllllll}n\equiv 1(\bmod\ 4),&&&n\equiv 2(\bmod\ 4),\\ f=\left(\begin{array}[]{cccccccc}1020&\cdots&1020&101\\ 0101&\cdots&0101&021\\ 2010&\cdots&2010&201\\ 0101&\cdots&0101&011\\ \vdots&\ddots&\vdots&\vdots\\ 1020&\cdots&1020&101\\ 0101&\cdots&0101&021\\ 2010&\cdots&2010&201\\ 0101&\cdots&0101&011\\ \hdashline 1020&\cdots&1020&102\\ \end{array}\right),&&&f=\left(\begin{array}[]{cccccc}1020&\cdots&1020&101\\ 0101&\cdots&0101&021\\ 2010&\cdots&2010&201\\ 0101&\cdots&0101&011\\ \vdots&\ddots&\vdots&\vdots\\ 1020&\cdots&1020&101\\ 0101&\cdots&0101&021\\ 2010&\cdots&2010&201\\ 0101&\cdots&0101&011\\ \hdashline 1020&\cdots&1020&101\\ 1101&\cdots&1101&020\\ \end{array}\right),\end{array}}

\displaystyle\small{\begin{array}[]{llllllllll}n\equiv 3(\bmod\ 4),&&&n\equiv 0(\bmod\ 4),\\ f=\left(\begin{array}[]{cccccccc}1020&\cdots&1020&101\\ 0101&\cdots&0101&021\\ 2010&\cdots&2010&201\\ 0101&\cdots&0101&011\\ \vdots&\ddots&\vdots&\vdots\\ 1020&\cdots&1020&101\\ 0101&\cdots&0101&021\\ 2010&\cdots&2010&201\\ 0101&\cdots&0101&011\\ \hdashline 1020&\cdots&1020&101\\ 0101&\cdots&0101&021\\ 2010&\cdots&2010&201\\ \end{array}\right),&&&f=\left(\begin{array}[]{cccccc}1020&\cdots&1020&101\\ 0101&\cdots&0101&021\\ 2010&\cdots&2010&201\\ 0101&\cdots&0101&011\\ \vdots&\ddots&\vdots&\vdots\\ 1020&\cdots&1020&101\\ 0101&\cdots&0101&021\\ 2010&\cdots&2010&201\\ 0101&\cdots&0101&011\\ \hdashline 1020&\cdots&1020&101\\ 0101&\cdots&0101&021\\ 2010&\cdots&2010&101\\ 0102&\cdots&0102&011\\ \end{array}\right).\end{array}}

Then the weight is

\small{w(f)=\left\{\begin{array}[]{lllllllll}\frac{m-3}{4}\times\frac{n-4}{4}\times 10+\frac{n-4}{4}\times 10+\frac{m-3}{4}\times 11+9=\frac{5mn+5n+2m-14}{8},&n\equiv 0(\bmod\ 4),\\ \frac{m-3}{4}\times\frac{n-1}{4}\times 10+\frac{n-1}{4}\times 10+\frac{m-3}{4}\times 3+3=\frac{5mn+5n+m+1}{8},&n\equiv 1(\bmod\ 4),\\ \frac{m-3}{4}\times\frac{n-2}{4}\times 10+\frac{n-2}{4}\times 10+\frac{m-3}{4}\times 6+4=\frac{5mn+5n+2m-14}{8},&n\equiv 2(\bmod\ 4),\\ \frac{m-3}{4}\times\frac{n-3}{4}\times 10+\frac{n-3}{4}\times 10+\frac{m-3}{4}\times 8+8=\frac{5mn+5n+m+1}{8},&n\equiv 3(\bmod\ 4).\\ \end{array}\right.}

Hence,

\small{\gamma_{oiR}(P_{n}\Box C_{m})\leq\left\{\begin{array}[]{lllllllll}\frac{5mn+5n+2m-14}{8},&n\equiv 0,2(\bmod 4),\\ \frac{5mn+5n+m+1}{8},&n\equiv 1,3(\bmod 4).\\ \end{array}\right.}

Therefore, $\gamma_{oiR}(P_{n}\Box C_{m})\leq\frac{5mn+5n+2m}{8}$ .

Acknowledgements.

The authors would like to thank the anonymous referee, whose suggestions greatly improved the exposition of this paper.

References

[1] Cockayne EJ, Dreyer Jr PA, Hedetniemi SM, Hedetniemi ST. Roman domination in graphs. Discrete mathematics, 2004. 278:11–22. 10.1016/j.disc.2003.06.004.
[2] Luiz AG. Roman domination and independent Roman domination on graphs with maximum degree three. Discrete Applied Mathematics, 2024. 348:260–278. 10.1016/j.dam.2024.02.006.
[3] Pavlič P, Žerovnik J. Roman domination number of the Cartesian products of paths and cycles. The Electronic Journal of Combinatorics, 2012. 19(3):P19. 10.37236/2595.
[4] Poureidi A, Rad NJ. Algorithmic and complexity aspects of problems related to total Roman domination for graphs. Journal of Combinatorial Optimization, 2020. 39(3):747–763. 10.1007/s10878-019-00514-x.
[5] Liu CA. Roman domination and double Roman domination numbers of Sierpiński graphs $S(K_{n},t)$ . Bulletin of the Malaysian Mathematical Sciences Society, 2021. 44(6):4043–4058. 10.1007/s40840-021-01136-5.
[6] Beeler RA, Haynes TW, Hedetniemi ST. Double Roman domination. Discrete Applied Mathematics, 2016. 211:23–29. 10.1016/j.dam.2016.03.017.
[7] Henning MA, Klostermeyer WF. Italian domination in trees. Discrete Applied Mathematics, 2017. 217:557–564. 10.1016/j.dam.2016.09.035.
[8] Abdollahzadeh Ahangar H, Álvarez MP, Chellali M, Sheikholeslami SM, Valenzuela-Tripodoro JC. Triple Roman domination in graphs. Applied Mathematics and Computation, 2021. 391:125444. 10.1016/j.amc.2020.125444.
[9] Yue J, Song J. Note on the perfect Roman domination number of graphs. Applied Mathematics and Computation, 2020. 364:124685. 10.1016/j.amc.2019.124685.
[10] Abdollahzadeh Ahangar H, Henning MA, Löwenstein C, Zhao Y, Samodivkin V. Signed Roman domination in graphs. Journal of Combinatorial Optimization, 2014. 27(2):241–255. 10.1007/s10878-012-9500-0.
[11] Abdollahzadeh Ahangar H, Chellali M, Samodivkin V. Outer independent Roman dominating functions in graphs. International Journal of Computer Mathematics, 2017. 94(12):2547–2557. 10.1080/00207160.2017.1301437.
[12] Martínez AC, García SC, García AC, Grisales del Rio AM. On the outer-independent Roman domination in graphs. Symmetry, 2020. 12(11):1846. 10.3390/sym12111846.
[13] Poureidi A, Ghaznavi M, Fathali J. Algorithmic complexity of outer independent Roman domination and outer independent total Roman domination. Journal of Combinatorial Optimization, 2021. 41:304–317. 10.1007/s10878-020-00682-1.
[14] Nazari-Moghaddam S, Sheikholeslami SM. On trees with equal Roman domination and outer-independent Roman domination number. Communications in Combinatorics and Optimization. 4(2):185–199. 10.22049/CCO.2019.26333.1097.
[15] Dehgardi N, Chellali M. Outer independent Roman domination number of trees. Communications in Combinatorics and Optimization, 2021. 6(2):273–286. 10.22049/CCO.2021.27072.1191.
[16] Rad NJ, Khodkar A, Kamarulhaili H. Bounds on the outer-independent Roman domination number of unicyclic and bicyclic graphs. Australasian Journal of Combinatorics, 2024. 88(3):385–397.
[17] Garzón EM, Martínez JA, Moreno JJ, Puertas ML. On the 2-domination number of cylinders with small cycles. Fundamenta Informaticae, 2022. 185(2):185–199. 10.3233/FI-222107.

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

Abstract

keywords:

1 Introduction

2 The outer independent Roman domination number of P1​□​CmP_{1}\Box C_{m}, P2​□​CmP_{2}\Box C_{m} and P3​□​CmP_{3}\Box C_{m}

Theorem 2.1

Proof 2.2

Theorem 2.3

Proof 2.4

Theorem 2.5

Proof 2.6

3 The outer independent Roman domination number of Pn​□​C3P_{n}\Box C_{3}

Theorem 3.1

Proof 3.2

4 Upper bounds on the outer independent Roman domination number of Pn​□​CmP_{n}\Box C_{m}, n,m≥4n,m\geq 4

Theorem 4.1

Proof 4.2

Acknowledgements.

References

2 The outer independent Roman domination number of $P_{1}\Box C_{m}$ , $P_{2}\Box C_{m}$ and $P_{3}\Box C_{m}$

3 The outer independent Roman domination number of $P_{n}\Box C_{3}$

4 Upper bounds on the outer independent Roman domination number of $P_{n}\Box C_{m}$ , $n,m\geq 4$