# The restrained double Roman domination
and graph operations

Zhipeng Gao1, Changqing Xi1, Jun Yue2
1Center for Combinatorics and LPMC, Nankai University, Tianjin, China
2 School of Mathematics and Statistics
Shandong Normal University, Jinan, Shandong 250358, P.R. China
Emails<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>

###### Abstract

Let $G=(V(G),E(G))$ be a simple graph. A restrained double Roman dominating
function (RDRD-function) of $G$ is a function $f:V(G)\rightarrow\\{0,1,2,3\\}$
satisfying the following properties: if $f(v)=0$, then the vertex $v$ has at
least two neighbours assigned 2 under $f$ or one neighbour $u$ with $f(u)=3$;
and if $f(v)=1$, then the vertex $v$ must have one neighbor $u$ with $f(u)\geq
2$; the induced graph by vertices assigned 0 under $f$ contains no isolated
vertex. The weight of a RDRD-function $f$ is the sum $f(V)=\sum_{v\in
V(G)}f(v)$, and the minimum weight of a RDRD-function on $G$ is the restrained
double Roman domination number (RDRD-number) of $G$, denoted by
$\gamma_{rdR}(G)$. In this paper, we first prove that the problem of computing
RDRD-number is NP-hard even for chordal graphs. And then we study the impact
of some graph operations, such as strong product, cardinal product and corona
with a graph, on restrained double Roman domination number.

AMS Math. Subj. Class. (2010): 05C69, 05C07 Keywords: double Roman domination,
restrained double Roman domination number, graph operations.

##  1 Introduction

Let $G=(V(G),E(G))$ be a simple graph with vertex set $V(G)$ and edge set
$E(G)$. We always denote $|V(G)|$ and $|E(G)|$ by order $n$ and size $m$,
respectively. For any vertex $v\in V(G)$, the _open neighborhood_ of $v$ is
the set $\\{u|(u,v)\in E\\}$, denoted by $N(v)$. The _degree_ of a vertex
$v\in V(G)$ is $d(v)=|N(v)|$ stands for the number of vertices in $N(v)$. The
minimum degree (resp., maximum degree) among the vertices of $G$ is denoted by
$\delta(G)$ (resp., $\Delta(G)$). A vertex $v$ with $d(v)=1$ is a _leaf_ , and
its neighbor is called a _support vertex_. If there are at least two leaves in
the neighborhood of a vertex $u$, then $u$ is called a _strong support
vertex_. A _wounded spider_ $ws(1,n,t)$ is a tree by subdividing $t$ edges of
the star $K_{1,n}$, where $0\leq t\leq n-1$. For more graph theoretic
terminology and notations not given here, the reader is referred to [22].

A subset $D$ of $V(G)$ is a _domination set_ if every vertex outside $D$ has a
neighbor in $D$. The _domination number_ of $G$, denoted by $\gamma(G)$, is
the minimum cardinality of a domination set of $G$. A domination set $D$ of
$G$ is a _restrained domination set_ if every vertex outside $D$ is adjacent
to another vertex in $V(G)\setminus D$. The _restrained domination number_ of
$G$, denoted by $\gamma_{r}(G)$, is the minimum cardinality of a restrained
domination set in $G$. The concept of the restrained domination was formally
introduced in [5]. Since then, the variants of restrained domination have
already been studied, the details refer to [3, 14, 15, 17].

Double Roman domination is a stronger version of Roman domination, which was
introduced in [2]. A _double Roman dominating function_ (for short, DRD-
function) of $G$ is a function $f:V(G)\rightarrow\\{0,1,2,3\\}$ satisfying the
following conditions: if $f(v)=0$, then the vertex $v$ has at least two
neighbours assigned 2 under $f$ or one neighbour $u$ with $f(u)=3$; and if
$f(v)=1$, then the vertex $v$ must have one neighbor $u$ with $f(u)\geq 2$. At
the same time, the DRD-function satisfying the subgraph induced by vertices
assigned 0 under $f$ contains no isolated vertex, we call it a _restrained
double Roman dominating function_ (RDRD-function) of $G$. Note that if any
vertex $v\in V(G)$ satisfying the above conditions is said to be _restrained
double Roman dominated_. The weight of an RDRD-function $f$ is the sum
$f(V)=\sum_{v\in V(H)}f(v)$, and the minimum weight of an RDRD-function on $G$
is the _restrained double Roman domination number_ (RDRD-number) of $G$,
denoted by $\gamma_{rdR}(G)$. For the sake of convenience, an RDRD-function
$f$ of a graph $G$ with weight $\gamma_{rdR}(G)$ is called a
$\gamma_{rdR}(G)$-function. Since a restrained double Roman dominating
function induces the ordered partition of $V(G)$ with $V_{i}=\\{v\in
V(G):f(v)=i\\}$ for $i=\\{0,1,2,3\\}$, we are allowed to write
$f=(V_{0},V_{1},V_{2},V_{3})$.

The concept of restrained double Roman domination was recently introduced by
Mojdeha, Masoumib and Volkmann in [13]. They proved that computing the value
of RDRD-number is NP-Complete for general graphs. Moreover, an upper bound on
RDRD-number of a connected graph $G$ was given, and characterization of the
graphs achieving the bound was presented. In addition, they compared the
parameters between RDRD-number and other domination numbers. And then, Samadi
et al. [18] proved that the problem of computing RDRD-number is NP-hard even
for planar graphs, and investigated its relationships with some well-known
parameters such as the restrained domination number and the domination number
for general graphs, respectively. They also gave the characterization of
graphs with small RDRD-numbers, which was independently given by Xi and Yue in
[23]. In [23], the authors gave a linear time algorithm for computing the
RDRD-number of a cograph.

The graph product is vital as the binary operation on graphs. Specially, it is
an operation that takes two graphs $G_{1}$ and $G_{2}$ and produces a new
graph with desired properties. By applying the graph product operations, we
can enlarge the smaller graphs, and can also identify and decompose the whole
graph with the help of factor graphs to understand the structure and
topological properties of the whole. Graph products have various applications
such as computer and communication networks, management of multiprocessors and
automata theory[7]. Now we give some definitions of the graph products as
follows. The cardinal product of two graphs $G$ and $H$ (called sometimes
direct product, cross product or Kronecker product), denoted by $G\times H$,
is the graph with $V(G\times H)=V(G)\times V(H)$ and
$(u,v)(u^{\prime},v^{\prime})\in E(G\times H)$ if $uu^{\prime}\in E(G)$ and
$vv^{\prime}\in E(H)$. The strong product of two graphs $G$ and $H$, denoted
by $G\boxtimes H$, is the graph with $V(G\boxtimes H)=V(G)\times V(H)$ and
$(u,v)(u^{\prime},v^{\prime})\in E(G\boxtimes H)$ if, either ($uu^{\prime}\in
E(G)$ and $v=v^{\prime}$), $(vv^{\prime}\in E(H)$ and $u=u^{\prime}$) or
($uu^{\prime}\in E(G)$ and $vv^{\prime}\in E(H)$). The corona of two graphs
$G$ and $H$, denoted by $G\odot H$, is the graph formed by taking one copy of
$G$, $|V(G)|$ copies of $H$, and then joining $i^{th}$ vertex of $V(G)$ to
every vertex in the $i^{th}$ copy of $H$. In particular, $G\odot K_{1}$ is the
graph constructed from one copy of $G$, and for each vertex $v\in V(G)$, a new
vertex $v^{\prime}$ as a leaf added.

Vizing’s conjecture on Cartesian product graphs has become one of the most
interesting problems of domination in graphs since it was introduced [20], and
it has motivated a large number of scholars to focus on the domination
problems of Cartesian product graphs. Another graph product that provides an
interesting and non-trivial problems on domination is the cardinal product. A
Vizing-like conjecture for the cardinal product was proposed in [8], namely
$\gamma(G\times H)\geq\gamma(G)\gamma(H)$. Subsequently, some researchers gave
a negative answer to the Vizing-like conjecture. This further reflects the
difficulty of studying the cardinal product of graphs. As Sandi Klavžar stated
in [8], “Although the direct product(cardinal product) of graphs is the most
natural graph product, it is also the most difficult and unpredictable among
standard graph products”.

Several scholars have discussed the properties and the domination number of
$P_{n}\times P_{m}$. Klobučar [9, 10] determined the exact values of the
domination number of $P_{n}\times P_{m}$ for $2\leq n\leq 6$, and also
presented the bounds of the domination numbers of $P_{7}\times P_{m}$ and
$P_{8}\times P_{m}$. Chérifi et al. [4] designed an algorithm to get the exact
values of the domination number of $P_{9}\times P_{m}$ for $m\geq 8$. Roman
domination in Cartesian product graphs and strong product graphs were studied
by Yero et al. [24]. Recently, the total Roman domination number of the graph
$G\times H$ was studied by Martǐnez et al. [12]. And they also studied the
cardinal product graphs $G\times H$ for various specific graphs. Klobučar et
al. [11] focused on the double Roman domination numbers on cardinal products
of graphs, and they obtained the exact values of $\gamma_{dR}(P_{2}\times G)$
for some special graphs $G$. Moreover, the exact values of
$\gamma_{dR}(P_{k}\times P_{n})$ were determined, where $k\in\\{2,3,4\\}$. In
addition, they presented the upper and lower bounds for
$\gamma_{dR}(P_{5}\times P_{n})$ and $\gamma_{dR}(P_{6}\times P_{n})$. In
[19], the impact of various graph operations on the double Roman domination
number was studied, including cartesian product, addition of twins and corona
with a graph. These results have laid the foundation for our research work.

In this paper, we will mainly consider the RDRD-number of graphs. In section
2, we prove that the problem of computing RDRD-number is NP-hard even for
chordal graphs. In section 3, we determine the exact values of RDRD-numbers of
graphs $P_{2}\boxtimes P_{m}$ and $P_{3}\boxtimes P_{m}$, where $m\geq 2$. In
section 4, we present an upper bound and a lower bound of RDRD-number of
$G\times H$ for any two graphs $G$ and $H$. And then, we obtain the exact
values of RDRD-number of $C_{3}\times C_{m}$ and $P_{2}\times G$ for some
special graph $G$, where $m\geq 3$. In the last section, we obtain the exact
value of RDRD-number of $G\odot H$ when $(H\ncong K_{1})$, and present the
sharp bounds of $G\odot K_{1}$. Moreover, the exact values of
$\gamma_{rdR}(G\odot K_{1})$ are determined, where $G$ is a complete graph, a
cycle, a path or a complete bipartite graph.

##  2 Complexity Result

In this section, we will prove that the decision problem associated with RDRD-
number is NP-Complete even for chordal graphs. That is stated in the following
decision problem, to which we shall refer as RDRD-Problem.

RDRD-Problem:

Instance:Given a chordal graph $G=(V,E)$.

Question: Is there a RDRD-function for $G$ whose weight is at most $k$?

We will show that this problem is NP-Complete by reducing the well-known NP-
Complete problem, Exact-3-Cover(X3C), to RDRD-Problem.

Exact-3-Cover(X3C):

Instance: A finite set $X$ with $|X|=3q$ and a collection $\mathcal{C}$ of
3-element subsets of $X$.

Question: Is there a subcollection $C^{\prime}$ of $C$ such that every element
of $X$ appears in exactly one element of $C^{\prime}$?

The ideal to prove the following theorem is similar to the proof of Theorem 5
in [1].

######  Theorem 2.1.

RDRD-Problem is NP-Complete for chordal graphs.

###### Proof.

RDRD-Problem belongs to $\mathcal{NP}$-class, since it is a polynomial time to
decide that a function is a RDRD-function with weight at most $k$. Now we show
how to transform any instance of X3C into an instance in RDRD-Problem
satisfying that one of them has a solution if and only if the other has a
solution.

Let $X=\\{x_{1},x_{2},\ldots,x_{3q}\\}$ and $C=\\{C_{1},C_{2},\ldots,C_{t}\\}$
be any arbitrary instance of X3C. We construct a chordal graph $G$ as follows.
First, we create a bipartite graph with vertices $x_{i}$ respect to each
$x_{i}\in X$ and $c_{i}$ respect to each $C_{i}\in C$, whose edge $x_{i}c_{j}$
if and only if $x_{j}\in C_{j}$, for $i\in[3q]$ and $j\in[t]$. Second, in the
so far constructed graph, add a pendant vertex $y_{i}$ to each vertex $x_{i}$,
create a new vertex $c^{\prime}_{j}$ which has the same neighbors of $c_{j}$,
where $i\in[3q]$ and $j\in[t]$. And then make
$B:=\\{c_{1},c_{2},\ldots,c_{t},c^{\prime}_{1},c^{\prime}_{2},\ldots,c^{\prime}_{t}\\}$
form a clique. Third, add new five vertices $z,z_{1},z_{2},z_{3},z_{4}$ such
that $z$ is adjacent to all vertices in $B$, $z,z_{1},z_{2}$ and
$z,z_{3},z_{4}$ are form triangles. It is easy to check that this graph is a
chordal graph. An example can be seen in Figure 2.1, where
$X=\\{x_{1},x_{2},\ldots,x_{6}\\}$ and
$C=\\{\\{x_{1},x_{3},x_{5}\\},\\{x_{2},x_{4},x_{6}\\}\\}$.

Figure 2.1: NP-Completeness for chordal graphs.

Let $k=8q+3$. Suppose that the instance $X$, $C$ of X3C has a solution
$C_{S}\subset C$. Let $Y=\\{y_{1},y_{2},\ldots,y_{3q}\\}$. We give a RDRD-
function $f$ on $G$ as follows.

${f(v)=\left\\{\begin{array}[]{llll}\vspace{0.1cm}3,&v=z,\\\ 2,&v\in Y\cup
C_{S},\\\ 0,&oterwise.\end{array}\right.}$

Clearly, $w(f)=2\times 3q+2\times q+3=8q+3=k$.

Conversely, suppose $G$ has a RDRD-function with weight at most $k$. Among all
such functions, let $g=(V_{0},V_{1},V_{2},V_{3})$ be a $\gamma_{rdR}$-function
chosen satisfying the conditions.

  * (C1)

$|Y\cap V_{3}|$ is minimized.

  * (C2)

Subject to Condition (C1): $|B\cap V_{3}|$ is minimized.

Denoted $V_{0}[B\cup X\setminus z]$ as the vertices labelled by 0 under $g$ in
$B\cup X\setminus z$. Since $y_{i}$ is a pendent vertex and the definition,
then $g(y_{i})\neq 0$, for $i\in[3q]$. First, we claim that $g(z)=3$ and
$g(v)=0$ for $v\in\\{z_{1},z_{2},z_{3},z_{4}\\}$. We will prove the claim as
follows. If $g(z)\neq 0$ or $g(z)=0$ and $G[V_{0}[B\cup X\setminus z]]$ has no
isolated vertex, then $w(g(z,z_{1},z_{2},z_{3},z_{4}))\geq 6$, we define a new
RDRD-function $g^{\prime}$ as reassigning $z$ with $3$, $z_{i}=0$ for
$i\in[4]$. And hence $w(g^{\prime})<w(g)$ for $G$, a contradiction. Otherwise,
there exists only one vertex in $B$ with labelled with 0, say
$c^{\prime}_{j}$. Now, we consider the weight under $g$ of the set
$S=\\{c_{j},c^{\prime}_{j},x_{i},y_{i},z,z_{1},z_{2},z_{3},z_{4}\\}$ is at
least 10, then we define a new RDRD-funciton $g^{\prime}$ as reassigning
$z=3$, $y_{i}=2$, $c_{j}=2$, the remaining vertices in $S$ with $0$. And hence
$w(g^{\prime})<w(g)$ for $G$, a contradiction. Note that every neighbor of $z$
can be defended by $z$, including vertices of $B$. Next, we want to prove that
$g(x_{i},y_{i})\in\\{2,3\\}$ for every $i\in[3q]$. By the definition of RDRD-
function, we know that $g(x_{i},y_{i})\geq 2$. Suppose $g(x_{i},y_{i})\geq 4$.
If $g(x_{i})=3$, then $g(y_{i})\geq 1$, and reassigning $x_{i}$ by 2, a
contradiction. If $g(x_{i})=2$, then $g(y_{i})\geq 2$, and reassigning $y_{i}$
by $1$, a contradiction. Finally, we claim that $g(v)\in\\{0,2\\}$ for $v\in
B$, and further $g(c_{j})=g(c^{\prime}_{j})=2$ is not exist for every
$i\in[t]$. If there exists some vertex $v\in B$ satisfying $g(v)=1$, then
reassigning $v$ by 0, a contradiction. Now suppose there exists a vertex $v\in
B$ with $g(v)=3$ and the three neighbors in $X$ of $v$ is denoted by
$x_{1},x_{2},x_{3}$. If $y_{i}=3$ for some $i\in[3]$, then reassigning
$y_{i}=2$, contradiction to (C1). Otherwise, reassigning $v=2$, it is still a
RDRD-function, contradiction to (c2). And further, if
$g(c_{j})=g(c^{\prime}_{j})=2$ for some $j\in[t]$. We redefine $g(c_{i})=2$
and $g(c^{\prime}_{i})=0$, then we get a RDRD-function with a smaller weight,
a contradiction.

Without loss of generality, we assume that $g(c^{\prime}_{j})=0$ for all
$j\in[t]$. Now assume that the number of $g(x_{i},y_{i})=2$ is $a$, and the
weight of each of the other $3q-a$ pairs is $3$. Let $b$ be the number of the
vertices labelled by 2 in $B$. Then

$3(3q-a)+2a+2b+3\leq 8q+3,$

which implies $a-2b\geq q$. Further, every vertex of $B$ has 3 neighbors in
$X$, thus $a\leq 3b$. Note that the fact $a\leq 3q$, we obtain $a=3q$ and
$b=q$. Consequently, $C_{S}=\\{C_{j}:g(c_{j})=2\\}$ is an exact cover of $C$.

∎

##  3 Strong Product

In this section, we first present some bounds on the restrained double Roman
domination number of strong product graphs, moreover we determine the exact
values of restrained double Roman domination numbers on $P_{2}\boxtimes P_{m}$
and $P_{3}\boxtimes P_{m}$. To begin with, we recall the following known
results.

######  Theorem 3.1.

[6] For any graphs $G$ and $H$,

$max\\{P_{2}(G)\gamma(H),\gamma(G)P_{2}(H)\\}\leq\gamma{(G\boxtimes H)}\leq
2\gamma(G)\gamma(H),$

where $P_{2}(G)$ is a 2-packing of a graph $G$, which is a set of vertices in
$G$ that are pair-wise at distance more that 2.

######  Theorem 3.2.

[13] For any connected graph $G$ of order $n\geq 3$, $\gamma_{rdR}(G)\leq
2n-2$.

######  Observation 3.3.

Let $G$ and $H$ be the connected graphs of order $n$ and $m$, respectively.
Then

$2max\\{P_{2}(G)\gamma(H),\gamma(G)P_{2}(H)\\}\leq\gamma_{rdR}{(G\boxtimes
H)}\leq 2nm-2.$

###### Proof.

Recall the inequality $2\gamma(G)\leq\gamma_{dR}(G)\leq\gamma_{rdR}(G)$ for
any graph $G$ and Theorem 3.1, the lower bound can be obtained. Further note
$V(G\boxtimes H)=|V(G)||V(H)|=nm$ and Theorem 3.2, the upper bound is an
immediate consequence. ∎

######  Lemma 3.4.

For any connected graphs $G$ and $H$, let $f_{1}=(A_{0},A_{1},A_{2},A_{3})$ be
a $\gamma_{rdR}(G)$-function and let $f_{2}=(B_{0},B_{1},B_{2},B_{3})$ be a
$\gamma_{rdR}(H)$-function. Then

$\displaystyle\gamma_{rdR}(G\boxtimes H)$
$\displaystyle\leq\gamma_{rdR}(G)\gamma_{rdR}(H)-6|A_{3}||B_{3}|-3|A_{3}||B_{2}|-2|A_{3}||B_{1}|-3|A_{2}||B_{3}|-2|A_{2}||B_{2}|-$
$\displaystyle\hskip 19.91692pt|A_{2}||B_{1}|-|A_{1}||B_{2}|-2|A_{1}||B_{3}|.$

###### Proof.

We define the function $f$ on $G\boxtimes H$ as follows.

${f(u,v)=\left\\{\begin{array}[]{llll}\vspace{0.1cm}3,&\hskip
5.69054pt(u,v)\in(A_{3}\times B_{3})\cup(A_{2}\times B_{3})\cup(A_{3}\times
B_{2}),\\\ 2,&\hskip 5.69054pt(u,v)\in(A_{2}\times B_{2}),\\\ 1,&\hskip
5.69054pt(u,v)\in(A_{1}\times B_{1})\cup(A_{1}\times B_{2})\cup(A_{1}\times
B_{3})\cup(A_{2}\times B_{1})\cup(A_{3}\times B_{1}),\\\ 0,&\hskip
5.69054ptotherwise.\end{array}\right.}$

Note that the set $(A_{0}\times B_{0})\cup(A_{0}\times B_{1})\cup(A_{1}\times
B_{0})\cup(A_{1}\times B_{1})$ can be restrained double Roman dominated by
$(A_{2}\times B_{2})\cup(A_{2}\times B_{3})\cup(A_{3}\times
B_{2})\cup(A_{3}\times B_{3})$, the set $(A_{0}\times B_{2})\cup(A_{1}\times
B_{2})$ can be restrained double Roman dominated by $(A_{2}\times
B_{2})\cup(A_{3}\times B_{2})$, the set $(A_{0}\times B_{3})\cup(A_{1}\times
B_{3})$ can be restrained double Roman dominated by $(A_{2}\times
B_{3})\cup(A_{3}\times B_{3})$, the set $(A_{2}\times B_{0})\cup(A_{2}\times
B_{1})$ can be restrained double Roman dominated by $(A_{2}\times
B_{2})\cup(A_{2}\times B_{3})$, and the set $(A_{3}\times
B_{0})\cup(A_{3}\times B_{1})$ can be restrained double Roman dominated by
$(A_{3}\times B_{2})\cup(A_{3}\times B_{3})$. Thus $f$ is a restrained double
Roman domination function on $G\boxtimes H$. Therefore, we have

$\displaystyle\gamma_{rdR}(G\boxtimes H)$ $\displaystyle\leq
3|A_{3}||B_{3}|+3|A_{2}||B_{3}|+3|A_{3}||B_{2}|+2|A_{2}||B_{2}|+|A_{1}||B_{1}|+|A_{1}||B_{2}|+$
$\displaystyle\hskip 19.91692pt|A_{1}||B_{3}|+|A_{2}||B_{1}|+|A_{3}||B_{1}|$
$\displaystyle=9|A_{3}||B_{3}|+6|A_{3}||B_{2}|+3|A_{3}||B_{1}|+6|A_{2}||B_{3}|+4|A_{2}||B_{2}|+2|A_{2}||B_{1}|+$
$\displaystyle\hskip
19.91692pt|A_{1}||B_{1}|+2|A_{1}||B_{2}|+3|A_{1}||B_{3}|-6|A_{3}||B_{3}|-3|A_{3}||B_{2}|-2|A_{3}||B_{1}|-$
$\displaystyle\hskip
14.22636pt3|A_{2}||B_{3}|-2|A_{2}||B_{2}|-|A_{2}||B_{1}|-|A_{1}||B_{2}|-2|A_{1}||B_{3}|$
$\displaystyle=3|A_{3}|(3|B_{3}|+2|B_{2}|+|B_{1}|)+2|A_{2}|(3|B_{3}|+2|B_{2}|+|B_{1}|)+|A_{1}|(3|B_{3}|+$
$\displaystyle\hskip
14.22636pt2|B_{2}|+|B_{1}|)-6|A_{3}||B_{3}|-3|A_{3}||B_{2}|-2|A_{3}||B_{1}|-3|A_{2}||B_{3}|-2|A_{2}||B_{2}|-$
$\displaystyle\hskip 14.22636pt|A_{2}||B_{1}|-|A_{1}||B_{2}|-2|A_{1}||B_{3}|$
$\displaystyle=(3|A_{3}|+2|A_{2}|+|A_{1}|)(3|B_{3}|+2|B_{2}|+|B_{1}|)-6|A_{3}||B_{3}|-3|A_{3}||B_{2}|-$
$\displaystyle\hskip
14.22636pt2|A_{3}||B_{1}|-3|A_{2}||B_{3}|-2|A_{2}||B_{2}|-|A_{2}||B_{1}|-|A_{1}||B_{2}|-2|A_{1}||B_{3}|$
$\displaystyle=\gamma_{rdR}(G)\gamma_{rdR}(H)-6|A_{3}||B_{3}|-3|A_{3}||B_{2}|-2|A_{3}||B_{1}|-3|A_{2}||B_{3}|-$
$\displaystyle\hskip
14.22636pt2|A_{2}||B_{2}|-|A_{2}||B_{1}|-|A_{1}||B_{2}|-2|A_{1}||B_{3}|.$

∎

Now we give the following theorem by using the above lemma.

######  Theorem 3.5.

For any connected graphs $G$ and $H$ of order $n\geq 3$ and $m\geq 3$
respectively, let $f_{1}=(A_{0},A_{1},A_{2},A_{3})$ be a
$\gamma_{rdR}(G)$-function and let $f_{2}=(B_{0},B_{1},B_{2},B_{3})$ be a
$\gamma_{rdR}(H)$-function. Then

$\displaystyle\gamma_{rdR}(G\boxtimes H)$
$\displaystyle\leq\gamma_{rdR}(G)\gamma_{rdR}(H)-6.$

###### Proof.

Note that the inequality in Lemma 3.4, we will prove the result by considering
the following cases.

Case 1. $|A_{3}|\geq 1$ and $|B_{3}|\geq 1$.

Obviously, the result holds by Lemma 3.4.

Case 2. Either $|A_{3}|=0$ or $|B_{3}|=0$.

Without loose of generality, we may assume $|A_{3}|=0$ and $|B_{3}|\geq 1$.
Note that there must be $|A_{2}|\neq 0$. If $|A_{2}|\geq 2$, then
$3|A_{2}||B_{3}|\geq 6$. The result holds. If $|A_{2}|=1$, then $|A_{1}|\geq
2$, since the order of $G$ is at least 3. It follows
$3|A_{2}||B_{3}|+2|A_{1}||B_{3}|\geq 7$. The result also holds. Similarly, the
desired result can be obtained when $|B_{3}|=0$ and $|A_{3}|\geq 1$.

Case 3. $|A_{3}|=|B_{3}|=0$.

We know that there must be $|A_{2}|\neq 0$ and $|B_{2}|\neq 0$. If
$|A_{2}|\geq 2$ and $|B_{2}|\geq 2$, then
$2|A_{2}||B_{2}|+|A_{2}||B_{1}|+|A_{1}||B_{2}|\geq 8$. The result holds. If
$|A_{2}|\geq 2$ and $|B_{2}|=1$, then there must be $|B_{1}|\geq 2$, since the
order of $H$ is at least 3. It follows
$2|A_{2}||B_{2}|+|A_{2}||B_{1}|+|A_{1}||B_{2}|\geq 8$. Similarly, the desired
result can be obtained if $|B_{2}|\geq 2$ and $|A_{2}|=1$. Now we consider the
only remaining case, that is, $|A_{2}|=|B_{2}|=1$, then there must be
$|A_{1}|\geq 2$ and $|B_{1}|\geq 2$. It follows
$2|A_{2}||B_{2}|+|A_{2}||B_{1}|+|A_{1}||B_{2}|\geq 6$. The theorem holds. ∎

The upper bound in Theorem 3.5 can be achieved. For instance, if $G$ and $H$
are graphs of order $n$ and $m$, where $n,m\geq 3$, containing a vertex of
degree $n-1$ and $m-1$ respectively, and there is no pendant edge in $G$ and
$H$. In such a case, $G\boxtimes H$ contains a vertex of degree $nm-1$ and
there is no pendant edge in $G\boxtimes H$, since $d_{G\boxtimes
H}(u,v)=d_{G}(u)d_{H}(v)+d_{G}(u)+d_{H}(v)$. Recall the result in [23], thus
we have $\gamma_{rdR}(G\boxtimes H)=3=\gamma_{rdR}(G)\gamma_{rdR}(H)-6=3\times
3-6$.

In the remaining part of this section, the exact values of
$\gamma_{rdR}(P_{2}\boxtimes P_{m})$ and $\gamma_{rdR}(P_{3}\boxtimes P_{m})$
are determined.

In the sequel, let $f$ be a $\gamma_{rdR}(P_{n}\boxtimes P_{m})$-function. We
denote the set of vertices on the $j$-th column
$\\{v_{0,j},\ldots,v_{n-1,j}\\}$, as $V^{j}$, that is
$V^{j}=\\{v_{i,j}:i\in\\{0,\ldots,n-1\\}\\}$, and the weight of the $j$-th
column $f_{j}=f(V^{j})=\sum\nolimits_{v_{i,j}\in{V^{j}}}f(v_{i,j})$. Figure
3.1 shows the graph of $P_{n}\boxtimes P_{m}$.

Figure 3.1: Graph $P_{n}\boxtimes P_{m}$.

######  Lemma 3.6.

Let $f$ be a $\gamma_{rdR}(P_{n}\boxtimes P_{m})$-function, where
$n=2~{}\text{or}~{}3$, the followings hold.

  1. (1)

$f_{j-1}+f_{j}+f_{j+1}\geq 3$ for $j\in\\{1,\ldots,m-2\\}$.

  2. (2)

$f_{0}+f_{1}\geq 3$ and $f_{n-2}+f_{n-1}\geq 3$.

###### Proof.

For $j\in\\{0,\ldots,m-1\\}$, if there exists a $j$ such that $0\leq f_{j}\leq
2$, then there must be a vertex $v\in V^{j}$ assigned $0$ or $1$. By the
definition of RDRD-function, $\sum_{u\in N[v]}f(u)\geq 3$. Note that
$N[v]\subseteq V^{j-1}\cup V^{j}\cup V^{j+1}$ for $j\in\\{1,\ldots,m-2\\}$,
thus $f_{j-1}+f_{j}+f_{j+1}\geq 3$. While if $v\in V^{0}$, then $N[v]\subseteq
V^{0}\cup V^{1}$, thus $f_{0}+f_{1}\geq 3$, Similarly we have
$f_{n-2}+f_{n-1}\geq 3$. ∎

######  Theorem 3.7.

For $n=2~{}\text{or}~{}3$,

${\gamma_{rdR}(P_{n}\boxtimes
P_{m})=\left\\{\begin{array}[]{llll}\vspace{0.1cm}m,&\hskip 5.69054ptm\equiv
0(\bmod\ 3),\\\ m+2,&\hskip 5.69054ptm\equiv 1(\bmod\ 3),\\\ m+1,&\hskip
5.69054ptm\equiv 2(\bmod\ 3).\end{array}\right.}$

###### Proof.

Let $G=P_{n}\boxtimes P_{m}$, where $n=2~{}\text{or}~{}3$. We obtain the upper
bounds of RDRD-numbers of $G$ through giving a RDRD-function on $G$ in the
following cases.

Case 1. $m\equiv 0(\bmod\ 3)$.

Define $f:V(G)\rightarrow\\{0,1,2,3\\}$ by $f(v_{1,3k+1})=3$ for
$k=0,\ldots,\frac{m}{3}-1$ and $f(v_{i,j})=0$ otherwise. Clearly $f$ is a
RDRD-function of $G$ with weight $\frac{m}{3}\times 3=m$, thus
$\gamma_{rdR}(G)\leq m$.

Case 2. $m\equiv 1(\bmod\ 3)$.

Define $f:V(G)\rightarrow\\{0,1,2,3\\}$ by $f(v_{1,3k+1})=3$ for
$k=0,\ldots,\lfloor\frac{m}{3}\rfloor-1$, $f(v_{1,m-2})=3$ and $f(v_{i,j})=0$
otherwise. Clearly $f$ is a RDRD-function of $G$ with weight
$\frac{m-4}{3}\times 3+6=m+2$, thus $\gamma_{rdR}(G)\leq m+2$.

Case 3. $m\equiv 2(\bmod\ 3)$.

Define $f:V(G)\rightarrow\\{0,1,2,3\\}$ by $f(v_{1,3k+1})=3$ for
$k=0,\ldots,\lfloor\frac{m}{3}\rfloor-1$, $f(v_{1,m-2})=3$ and $f(v_{i,j})=0$
otherwise. Clearly $f$ is a RDRD-function of $G$ with weight
$\frac{m-2}{3}\times 3+3=m+1$, thus $\gamma_{rdR}(G)\leq m+1$.

Now we prove the inverse inequality. For $n\equiv 0(\bmod\ 3)$, by Lemma 3.6
(1), we can obtain that
$f(V)=\sum\nolimits_{j=0}^{m-1}f_{j}\geq\frac{m}{3}\times 3=m$, that is
$\gamma_{rdR}(G)\geq m$.

For $n\equiv 1(\bmod\ 3)$, by Lemma 3.6 (2), $f_{0}+f_{1}\geq 3$ and
$f_{m-2}+f_{m-1}\geq 3$, we have

$\displaystyle f(V)$
$\displaystyle=\sum\nolimits_{j=0}^{m-1}f_{j}=(f_{0}+f_{1}+f_{m-2}+f_{m-1})+\sum\nolimits_{j\in\\{2,\ldots,m-3\\}}f_{j}$
$\displaystyle\geq 3+3+\frac{m-4}{3}\times 3$ $\displaystyle=m+2.$

Thus $\gamma_{rdR}(G)\geq m+2$.

For $n\equiv 2(\bmod\ 3)$, by Lemma 3.6 (2), $f_{0}+f_{1}\geq 3$, we have

$\displaystyle f(V)$
$\displaystyle=\sum\nolimits_{j=0}^{m-1}f_{j}=(f_{0}+f_{1})+\sum\nolimits_{j\in\\{2,\ldots,m-1\\}}f_{j}$
$\displaystyle\geq 3+\frac{m-2}{3}\times 3$ $\displaystyle=m+1.$

Thus $\gamma_{rdR}(G)\geq m+1$.

From the above, the result holds. ∎

##  4 Cardinal Product

In this section, we study the restrained double Roman domination number of
$G\times H$. For any two graphs, we present an upper bound and a lower bound
of $\gamma_{rdR}(G\times H)$. Also we obtain the exact values of
$\gamma_{rdR}(P_{2}\times G)$ for many types of graph $G$. Further, we
determine the exact value of $\gamma_{rdR}(C_{3}\times C_{m})$ by using a
bagging approach.

We begin with the following known proposition.

######  Proposition 4.1.

[13]

  * (1)

For a path $P_{n}$ $(n\geq 4)$, $\gamma_{rdR}(P_{n})=n+2.$

  * (2)

For a cycle $C_{n}$ $(n\geq 3)$,

${\gamma_{rdR}(C_{n})=\left\\{\begin{array}[]{llll}\vspace{0.1cm}n,&\hskip
5.69054ptn\equiv 0(\bmod\ 3),\\\ n+2,&\hskip
5.69054ptotherwise.\end{array}\right.}$

######  Observation 4.2.

Let $G$ and $H$ be the graphs of order $n$ and $m$, respectively. Then

$\gamma_{rdR}(G\times H)\geq\lceil\frac{3nm}{\Delta(G)\Delta(H)+1}\rceil,$

In particular, if $G\times H$ is connected, then

$\gamma_{rdR}(G\times H)\leq 2nm-2.$

###### Proof.

In [21], Lutz Volkman proved that for any graph $G$ of order $n$ and
$\Delta(G)\geq 1$, $\gamma_{dR}(G)\geq\lceil\frac{3n}{\Delta(G)+1}\rceil.$
Since $\Delta(G\times H)=\Delta(G)\Delta(H)$ and
$\gamma_{rdR}(G)\geq\gamma_{dR}(G)$, we get

$\gamma_{rdR}(G\times H)\geq\lceil\frac{3nm}{\Delta(G)\Delta(H)+1}\rceil.$

Recall the upper bound of $\gamma_{rdR}(G)$ for any connected graph of order
at least $3$ in Theorem 3.2, $\gamma_{rdR}(G)\leq 2|V(G)|-2$. Further
$V(G\times H)=|V(G)||V(H)|=nm$ for any two graphs. Thus we get

$\gamma_{rdR}(G\times H)\leq 2nm-2.$

∎

######  Theorem 4.3.

For any tree $T$ and any graph $G$ without odd cycle, we have

$\gamma_{rdR}(P_{2}\times
T)=2\gamma_{rdR}(T)<\gamma_{rdR}(P_{2})\cdot\gamma_{rdR}(T),$
$\gamma_{rdR}(P_{2}\times
G)=2\gamma_{rdR}(G)<\gamma_{rdR}(P_{2})\cdot\gamma_{rdR}(G).$

###### Proof.

For cardinal product $G\times H$, if $G$ and $H$ are both bipartite, then
$G\times H$ consists of two connected components. Further $P_{2}\times T$ and
$P_{2}\times G$ consist of two disjoint copies of $T$ and $G$ respectively.
Note that $\gamma_{rdR}(P_{2})=3$, thus the theorem holds. ∎

By Proposition 4.1, we have Corollary 4.4.

######  Corollary 4.4.

${\gamma_{rdR}(P_{2}\times
P_{n})=\left\\{\begin{array}[]{llll}\vspace{0.1cm}2n+4,&n\geq 4,\\\
2n+2,&n\leq 3.\end{array}\right.}$

######  Theorem 4.5.

For cardinal product of $P_{2}$ and $C_{2n+1}$, where $n\geq 1$,

${\gamma_{rdR}(P_{2}\times
C_{2n+1})=\left\\{\begin{array}[]{llll}\vspace{0.1cm}4n+2,&n\equiv 0(\bmod\
6),\\\ 4n+4,&otherwise.\end{array}\right.}$

###### Proof.

For cardinal product $G\times H$, if $G$ and $H$ are not both bipartite, then
$G\times H$ is connected. Further $P_{2}\times C_{2n+1}$ is connected and is a
cycle $C_{4n+2}$. By Proposition 4.1, we can obtain that
$\gamma_{rdR}(P_{2}\times C_{2n+1})=4n+2$ for $n\equiv 0(\bmod\ 6)$,
$\gamma_{rdR}(P_{2}\times C_{2n+1})=4n+4$ otherwise. ∎

In the remaining part of this section, we determine the exact value of
$\gamma_{rdR}(C_{3}\times C_{m})$ by using a bagging approach. Figure 4.1(a)
shows the graph of $C_{3}\times C_{m}$. For more convenience and
intuitiveness, we add virtual auxiliary rows and columns as shown in Figure
4.1(b).

Figure 4.1: Graph $C_{3}\times C_{m}$.

In the sequel, let $f$ be an arbitrary restrained double Roman domination
function of $C_{3}\times C_{m}$. We denote the set of vertices on the $j$-th
column, $\\{v_{0,j},v_{1,j},v_{2,j}\\}$, as $V^{j}$, that is
$V^{j}=\\{v_{i,j}:i\in\\{0,1,2\\}\\}$, and the weight of the $j$-th column
$f_{j}=f(V^{j})=\sum\nolimits_{v_{i,j}\in{V^{j}}}f(v_{i,j})$.

######  Lemma 4.6.

For the graph $C_{3}\times C_{m}$, the following results hold.

  1. (L1)

If $f_{j}=0$, then $f_{j-1}+f_{j+1}\geq 6$.

  2. (L2)

If $f_{j}=1$, then $f_{j-1}+f_{j+1}\geq 5$.

  3. (L3)

If $f_{j}=3$, then $f_{j-1}+f_{j+1}\geq 3$.

  4. (L4)

If $4\leq f_{j}\leq 5$, then $f_{j-1}\geq 2$ or $f_{j+1}\geq 2$ holds.

where $0\leq j\leq m-1$ and subscripts are taken modulo $m$.

###### Proof.

  1. (L1)

$f_{j}=0$ holds for any $0\leq j\leq m-1$. Without lose of generality, we may
assume $f(v_{0,j-1})=0$, since $N(v_{1,j})\cap V_{0}\neq\emptyset$. By the
definition of RDRD-function, we know that
$f(v_{2,j-1})+f(v_{2,j+1})+f(v_{1,j-1})+f(v_{1,j+1})\geq 3$,
$f(v_{0,j+1})+f(v_{2,j-1})+f(v_{2,j+1})\geq 3$ and
$f(v_{1,j-1})+f(v_{1,j+1})+f(v_{0,j+1})\geq 3$. Now we prove the result by
considering the following cases.

Case 1.1. $f(v_{2,j-1})+f(v_{2,j+1})\geq 3$.

If $f(v_{2,j-1})+f(v_{2,j+1})\geq 3$, then $f_{j-1}+f_{j+1}\geq
f(v_{1,j-1})+f(v_{1,j+1})+f(v_{0,j+1})+f(v_{2,j-1})+f(v_{2,j+1})\geq 3+3=6$.
The result holds.

Case 1.2. $f(v_{2,j-1})+f(v_{2,j+1})=2$.

If $f(v_{2,j-1})+f(v_{2,j+1})=2$, then consider $v_{0,j}$ and $v_{1,j}$ should
be dominated, there are $f(v_{1,j-1})+f(v_{1,j+1})\geq 2$ and
$f(v_{0,j+1})\geq 2$ respectively. It follows
$f(v_{0,j+1})+f(v_{1,j-1})+f(v_{1,j+1})\geq 2+2=4$. Thus
$f(v_{0,j+1})+f(v_{1,j-1})+f(v_{1,j+1})+f(v_{2,j-1})+f(v_{2,j+1})\geq 2+4=6.$
The result holds.

Case 1.3. $f(v_{2,j-1})+f(v_{2,j+1})\leq 1$.

If $f(v_{2,j-1})+f(v_{2,j+1})\leq 1$, consider $v_{0,j}$ and $v_{1,j}$ should
be dominated, there are $f(v_{1,j-1})+f(v_{1,j+1})\geq 3$ and $f(v_{0,j+1})=3$
respectively. It follows $f(v_{0,j+1})+f(v_{1,j-1})+f(v_{1,j+1})\geq 3+3=6$.
Thus the result also holds.

  2. (L2)

$f_{j}=1$. If there exists a $j$ such that $f_{j}=1$, assume $f(v_{0,j})=1$.
Note that $N(v_{1,j})\cup V_{0}\neq\emptyset$, without lose of generality, we
may assume $f(v_{0,j-1})=0$ or $f(v_{2,j-1})=0$.

Case 2.1. $f(v_{0,j-1})=0$. By the definition of RDRD function,
$f(v_{2,j-1})+f(v_{2,j+1})+f(v_{1,j-1})+f(v_{1,j+1})\geq 2$,
$f(v_{0,j+1})+f(v_{2,j-1})+f(v_{2,j+1})\geq 3$ and
$f(v_{1,j-1})+f(v_{1,j+1})+f(v_{0,j+1})\geq 3$. Now we consider the following
subcases for $f(v_{2,j-1})+f(v_{2,j+1})$.

Case 2.1.1. $f(v_{2,j-1})+f(v_{2,j+1})\geq 2$. If
$f(v_{2,j-1})+f(v_{2,j+1})\geq 2$, then
$f(v_{1,j-1})+f(v_{1,j+1})+f(v_{0,j+1})+f(v_{2,j-1})+f(v_{2,j+1})\geq 3+2=5$.
Thus the result holds.

Case 2.1.2. $f(v_{2,j-1})+f(v_{2,j+1})\leq 1$. If
$f(v_{2,j-1})+f(v_{2,j+1})\leq 1$, then consider $v_{0,j}$ and $v_{1,j}$
should be dominated, there are $f(v_{1,j-1})+f(v_{1,j+1})\geq 2$ and
$f(v_{0,j+1})=3$ respectively. It follows
$f(v_{0,j+1})+f(v_{1,j-1})+f(v_{1,j+1})\geq 3+2=5$. Thus the result also
holds.

Case 2.2. $f(v_{2,j-1})=0$. By the definition of RDRD function,
$f(v_{2,j+1})+f(v_{1,j-1})+f(v_{1,j+1})\geq 2$,
$f(v_{0,j-1})+f(v_{0,j+1})+f(v_{2,j+1})\geq 3$ and
$f(v_{1,j-1})+f(v_{1,j+1})+f(v_{0,j-1})+f(v_{0,j+1})\geq 3$. Now we consider
the following subcases for $f(v_{1,j-1})+f(v_{1,j+1})$.

Case 2.2.1. $f(v_{1,j-1})+f(v_{1,j+1})\geq 2$. If
$f(v_{1,j-1})+f(v_{1,j+1})\geq 2$, then
$f(v_{1,j-1})+f(v_{1,j+1})+f(v_{0,j-1})+f(v_{0,j+1})+f(v_{2,j+1})\geq 2+3=5$.
Thus the result holds.

Case 2.2.2. $f(v_{1,j-1})+f(v_{1,j+1})\leq 1$. If
$f(v_{1,j-1})+f(v_{1,j+1})\leq 1$, then consider $v_{0,j}$ and $v_{2,j}$
should be dominated, there are $f(v_{2,j+1})=3$ and
$f(v_{0,j-1})+f(v_{0,j+1})\geq 3$ respectively. It follows
$f(v_{2,j+1})+f(v_{0,j-1})+f(v_{0,j+1})\geq 3+3=6$. Thus the result also
holds.

  3. (L3)

$f_{j}=3$. If there exists a $j$ such that $f_{j}=3$, then there must be at
least a vertex $v\in V^{j}$ assigned $0$ or $1$. If there exists a vertex
assigned $0$, then $f_{j-1}+f_{j+1}\geq 3$. If there is no vertex assigned $1$
in $V^{j}$, then by the definition of RDRD function,
$f(v_{2,j-1})+f(v_{2,j+1})+f(v_{1,j-1})+f(v_{1,j+1})\geq 2$,
$f(v_{0,j-1})+f(v_{0,j+1})+f(v_{2,j-1})+f(v_{2,j+1})\geq 2$ and
$f(v_{1,j-1})+f(v_{1,j+1})+f(v_{0,j-1})+f(v_{0,j+1})\geq 2$. Sum the above
inequalities, $2(f_{j-1}+f_{j+1})\geq 6$, $f_{j-1}+f_{j+1}\geq 3$. The result
holds.

  4. (L4)

$4\leq f_{j}\leq 5$. If there exists a $j$ such that $4\leq f_{j}\leq 5$, then
there must be at least a vertex $v\in V^{j}$ assigned $0$ or $1$. By the
definition of RDRD function, there are at least $f_{j-1}\geq 2$ or
$f_{j+1}\geq 2$. The result holds.

∎

######  Theorem 4.7.

For $m\geq 3$, $\gamma_{rdR}(C_{3}\times C_{m})=2m.$

###### Proof.

By L1 and L2 in Lemma 4.6, for each $f_{j}\leq 1$, there must be $f_{j-1}\geq
3$ or $f_{j+1}\geq 3$. Therefore we use the bagging approach to put $V^{j}$
$(0\leq j\leq m-1)$ into five $B_{s}$ bags. Actually, we collect vertices with
the column weights at least $3$ and vertices with the column weights at most
$1$ into one of the corresponding $B_{s}$ bags according to different cases.
We can find that the average of the weights of all columns in the same bag is
at least 2. In this process, if the vertices in a column $j$ have not been
bagged, we denote $D[j]=0$, otherwise $D[j]=1$.

Algorithm Procedure 1 Bagging Approach for $C_{3}\times C_{m}$

1: Initialization: $s=s_{1}=s_{2}=s_{3}=s_{4}=0$; $D[j]=0$ for $j=0$ up to
$j=m-1$;

2: for every $j$ with $f_{j}\geq 6\wedge D[j]=0$ do

3: $s=s+1$; $D[j]=1$; $B_{s}=V^{j}$;

4: if $f_{j-1}\leq 1$ then

5: $B_{s}=B_{s}\cup V^{j-1}$;$D[j-1]=1$;

6: end if

7: if $f_{j+1}\leq 1$ then

8: $B_{s}=B_{s}\cup V^{j+1}$;$D[j+1]=1$;

9: end if

10:
$\sum_{V^{j}\subseteq\cup_{t=1}^{s}B_{t}}f(j)\geq\frac{|\cup_{t=1}^{s}B_{t}|}{3}\times
2$; $s_{1}=s$;

11: end for

12: for every $j$ with $4\leq f_{j}\leq 5\wedge D[j]=0$ do

13: $s=s+1$; $D[j]=1$; $B_{s}=V^{j}$;

14: if $f_{j-1}\leq 1$, by L4, $f_{j+1}\geq 2$ then

15: $B_{s}=B_{s}\cup V^{j-1}$;$D[j-1]=1$;

16: end if

17: if $f_{j+1}\leq 1$, by L4, $f_{j-1}\geq 2$ then

18: $B_{s}=B_{s}\cup V^{j+1}$;$D[j+1]=1$;

19: end if

20:
$\sum_{V^{j}\subseteq\cup_{t=s_{1}+1}^{s}B_{t}}f(j)\geq\frac{|\cup_{t={s_{1}+1}}^{s}B_{t}|}{3}\times
2$; $s_{2}=s$;

21: end for

22: for every $j$ with $f_{j}=3\wedge D[j]=0$ do

23: $s=s+1$; $D[j]=1$; $B_{s}=V^{j}$;

24: if $f_{j-1}=1$, by L3, $f_{j+1}\geq 2$ then

25: $B_{s}=B_{s}\cup V^{j-1}$;$D[j-1]=1$;

26: end if

27: if $f_{j+1}=1$, by L3, $f^{j-1}\geq 2$ then

28: $B_{s}=B_{s}\cup V^{j+1}$;$D[j+1]=1$;

29: end if

30:
$\sum_{V^{j}\subseteq\cup_{t=s_{2}+1}^{s}B_{t}}f(j)\geq\frac{|\cup_{t={s_{2}+1}}^{s}B_{t}|}{3}\times
2$; $s_{3}=s$;

31: end for

32: for every $j$ with $f_{j}=3\wedge D[j]=0$ do

33: $s=s+1$; $D[j]=1$; $B_{s}=V^{j}$;

34: if $f_{j-1}=0$, by L1 and L3, $f_{j-2}\geq 3$, $f_{j+1}\geq 3$ then

35: $B_{s}=B_{s}\cup V^{j-1}\cup V^{j-2}$;$D[j-1]=D[j-2]=1$;

36: end if

37: if $f_{j+1}=0$, by L1 and L3, $f_{j-1}\geq 3$, $f_{j+2}\geq 3$ then

38: $B_{s}=B_{s}\cup V^{j+1}\cup V^{j+2}$;$D[j+1]=D[j+2]=1$;

39: end if

40:
$\sum_{V^{j}\subseteq\cup_{t=s_{3}+1}^{s}B_{t}}f(j)\geq\frac{|\cup_{t={s_{3}+1}}^{s}B_{t}|}{3}\times
2$; $s_{4}=s$;

41: end for

42: for every $j$ with $f_{j}=2\wedge D[j]=0$ do

43: $s=s+1$; $D[j]=1$; $B_{s}=V^{j}$;

44:
$\sum_{V^{j}\subseteq\cup_{t=s_{4}+1}^{s}B_{t}}f(j)\geq\frac{|\cup_{t={s_{4}+1}}^{s}B_{t}|}{3}\times
2$;

45: end for

Thus we have

$\begin{array}[]{lll}\vspace{0.1cm}f(V)&=&\sum_{i=0}^{m-1}f(j)\\\
&=&\sum_{V^{j}\subseteq\cup_{t=1}^{s_{1}}B_{t}}f(j)+\sum_{V^{j}\subseteq\cup_{t=s_{1}+1}^{s_{2}}B_{t}}f(j)+\sum_{V^{j}\subseteq\cup_{t=s_{2}+1}^{s_{3}}B_{t}}f(j)\\\
\vspace{0.1cm}&+&\sum_{V^{j}\subseteq\cup_{t=s_{3}+1}^{s_{4}}B_{t}}f(j)+\sum_{V^{j}\subseteq\cup_{t=s_{4}+1}^{s}B_{t}}f(j)\\\
\vspace{0.1cm}&\geq&\frac{|\cup_{t=1}^{s_{1}}B_{t}|}{3}\times
2+\frac{|\cup_{t={s_{1}+1}}^{s_{2}}B_{t}|}{3}\times
2+\frac{|\cup_{t={s_{2}+1}}^{s_{3}}B_{t}|}{3}\times
2+\frac{|\cup_{t={s_{3}+1}}^{s_{4}}B_{t}|}{3}\times
2+\frac{|\cup_{t={s_{4}+1}}^{s}B_{t}|}{3}\times 2\\\ &\geq&2m.\end{array}$

Define $f:V(C_{3}\times C_{m})\rightarrow\\{0,1,2,3\\}$ by $f(v_{1,j})=2$ for
$j\in\\{0,\ldots,m-1\\}$, $f(v_{i,j})=0$ otherwise. One can check that it is a
RDRD-function on $C_{3}\times C_{m}$ with weight $2m$, thus
$\gamma_{rdR}(C_{3}\times C_{m})\leq 2m$. Therefore, $\gamma_{rdR}(C_{3}\times
C_{m})=2m$. ∎

##  5 Corona Operator

In this section, we study the restrained double Roman domination number of
$G\odot H$ for any graph $G$ and $H$. We obtain the exact values of
$\gamma_{rdR}(G\odot H)$ when $(H\ncong K_{1})$, and present the sharp bounds
of $\gamma_{rdR}(G\odot K_{1})$. Further, the exact values of
$\gamma_{rdR}(G\odot K_{1})$ where $G$ is a complete graph, a cycle, a path or
a complete bipartite graph are determined. In addition, we present the
restrained double Roman domination number of $(G\odot K_{1})\odot K_{1}$.

######  Theorem 5.1.

For any connected graphs $G$ and any $H\ncong K_{1}$, then
$\gamma_{rdR}(G\odot H)=3n$, where $n=|V(G)|$.

###### Proof.

A RDRD-function of $G\odot H$ can be obtained by assigning $3$ to all vertices
of $G$, and $0$ to the remaining vertices in $G\odot H$. Thus
$\gamma_{rdR}(G\odot H)\leq 3n$. Conversely, the $n$ copies of $H$ are
pairwise disjoint in $G\odot H$. And further, each copy need a weight of at
least 3, since the definition of a RDRD-function and $H\ncong K_{1}$. It
follows that $\gamma_{rdR}(G\odot H)\geq 3n$. Thus the theorem holds. ∎

######  Theorem 5.2.

For any connected graph $G$ of order $n$, then $2n+1\leq\gamma_{rdR}(G\odot
K_{1})\leq 3n$.

###### Proof.

For $G\ncong K_{1}$, a RDRD-function can be obtained by assigning 3 to the
pendant vertices of $G\odot K_{1}$, and $0$ to the remaining vertices.
Otherwise, we assign 1 and 2 to the two vertices respectively. Thus
$\gamma_{rdR}(G\odot K_{1})\leq 3n$, where $n$ is the order of $G$. Now we
prove the inverse inequality. Each pendant vertex of $G\odot K_{1}$ belongs to
either $V_{2}\cup V_{3}$ or $V_{1}$ adjacent to the vertex in $V_{2}\cup
V_{3}$. We claim that if all pendant vertices are assigned $2$, then at least
one vertex in $G$ is assigned the value not less than 1. Otherwise, all
vertices assigned $0$ in $G$ cannot be restrained double Roman dominated,
which contradicts the definition of the RDRD-function. Thus
$\gamma_{rdR}(G\odot H)\geq 2n+1$. ∎

Thereafter we show the bounds in Theorem 5.2 are sharp.

######  Theorem 5.3.

${\gamma_{rdR}(K_{n}\odot
K_{1})=\left\\{\begin{array}[]{llll}\vspace{0.1cm}2n+1,&if\hskip
5.69054ptn\neq 2,\\\ 6,&if\hskip 5.69054ptn=2.\end{array}\right.}$

###### Proof.

It is easy to see $\gamma_{rdR}(K_{2}\odot K_{1})=6$. For $K_{n}\odot K_{1}$
$(n\neq 2)$, we assign 1 to a pendant vertex, 2 to its neighbor and the
remaining pendant vertices, and 0 otherwise. It is a RDRD-function of
$K_{n}\odot K_{1}$ $(n\neq 2)$ and thus $\gamma_{rdR}(K_{n}\odot K_{1})\leq
2n+1.$ By Proposition 5.2, we can obtain $\gamma_{rdR}(K_{n}\odot K_{1})=2n+1$
when $n\neq 2$. ∎

The exact value of double Roman domination number on $C_{n}\odot K_{1}$ is
obtained by Anu V. and Aparna Lakshmanan S. [19]. In the sequel, we determine
the exact values of restrained double Roman domination number on $C_{n}\odot
K_{1}$ and $P_{n}\odot K_{1}$.

######  Theorem 5.4.

[19]

${\gamma_{dR}(C_{n}\odot
K_{1})=\left\\{\begin{array}[]{llll}\vspace{0.1cm}\frac{7n}{3},&if\hskip
5.69054ptn=3k,\\\ \vspace{0.1cm}\frac{7n+2}{3},&if\hskip 5.69054ptn=3k+1,\\\
\frac{7n+1}{3},&if\hskip 5.69054ptn=3k+2,\\\ \end{array}\right.}$

That is $\gamma_{dR}(C_{n}\odot K_{1})=\lceil\frac{7n}{3}\rceil$.

In the sequel, for $G\in\\{C_{n},P_{n}\\}$, let $u_{i}\in V(G)$,
${u_{i}}^{\prime}$ be the leaf neighbors of $u_{i}$ in $G\odot K_{1}$, where
$i\in\\{1,\ldots,n\\}$. Let $f$ be an arbitrary RDRD-function on $G\odot
K_{1}$, we denote $f_{j}=f(u_{j})+f({u^{\prime}_{j}})$ $(1\leq j\leq n)$ and
$f(V)=\sum_{j=1}^{n}(f_{j})$.

######  Lemma 5.5.

For an arbitrary RDRD-function $f$ on $G\odot K_{1}$, we have

  1. (1)

If $G=C_{n}$, then $f_{j}+f_{j+1}+f_{j+2}\geq 7$, where $1\leq j\leq n$ and
subscripts are taken modulo $n$.

  2. (2)

If $G=P_{n}$, then $f_{j}+f_{j+1}+f_{j+2}\geq 7$, where $1\leq j\leq n-2$.

###### Proof.

By the definition of RDRD-function, we can easily get $f_{j}\geq 2$$(1\leq
j\leq n)$, so $f_{j}+f_{j+1}+f_{j+2}\geq 6$. Suppose
$f_{j}+f_{j+1}+f_{j+2}=6$, it means that $f_{j}=f_{j+1}=f_{j+2}=2$. The only
possible case is $f(u_{j})=f(u_{j+1})=f(u_{j+2})=0$ and
$f({u^{\prime}_{j}})=f({u^{\prime}_{j+1}})=f({u^{\prime}_{j+2}})=2$. In this
case, $u_{j+1}$ cannot be dominated, a contradiction. Thus
$f_{j}+f_{j+1}+f_{j+2}\geq 7$. Furthermore, the results in Lemma 5.5 (1) and
(2) are true for $C_{n}\odot K_{1}$ and $P_{n}\odot K_{1}$ respectively. ∎

######  Theorem 5.6.

${\gamma_{rdR}(C_{n}\odot
K_{1})=\left\\{\begin{array}[]{llll}\vspace{0.1cm}\lceil\frac{7n}{3}\rceil,&if\hskip
5.69054ptn\equiv 0,1(\bmod 3),\\\ \lceil\frac{7n}{3}\rceil+1,&if\hskip
5.69054ptn\equiv 2(\bmod 3).\end{array}\right.}$

###### Proof.

Figure 5.1 shows the graph of $C_{n}\odot K_{1}$.

Figure 5.1: Graph $C_{n}\odot K_{1}$.

Case 1. $n\equiv 0(\bmod\ 3)$. Define $f:V(C_{n}\odot
K_{1})\rightarrow\\{0,1,2,3\\}$ by
$f(u_{3k+3})=f(u^{\prime}_{3k+1})=f(u^{\prime}_{3k+2})=2$,
$f(u^{\prime}_{3k+3})=1$ for $k=0,\ldots,\frac{n}{3}-1$ and
$f(u_{i})=f(u^{\prime}_{i})=0$ otherwise. It is clear that $f$ is a RDRD-
function of $C_{n}\odot K_{1}$ with weight $\frac{7n}{3}$, thus
$\gamma_{rdR}(C_{n}\odot K_{1})\leq\frac{7n}{3}$.

Case 2. $n\equiv 1(\bmod\ 3)$. Define $f:V(C_{n}\odot
K_{1})\rightarrow\\{0,1,2,3\\}$ by
$f(u_{3k+3})=f(u^{\prime}_{3k+1})=f(u^{\prime}_{3k+2})=f(u_{n})=2$,
$f(u^{\prime}_{3k+3})=f(u^{\prime}_{n})=1$ for
$k=0,\ldots,\lfloor\frac{n}{3}\rfloor-1$ and $f(u_{i})=f(u^{\prime}_{i})=0$
otherwise. It is clear that $f$ is a RDRD-function of $C_{n}\odot K_{1}$ with
$f(V)=\frac{n-1}{3}\times 7+3=\frac{7n+2}{3}=\lceil\frac{7n}{3}\rceil$, thus
$\gamma_{rdR}(C_{n}\odot K_{1})\leq\lceil\frac{7n}{3}\rceil$.

Case 3. $n\equiv 2(\bmod\ 3)$. Define $f:V(C_{n}\odot
K_{1})\rightarrow\\{0,1,2,3\\}$ by
$f(u_{3k+3})=f(u^{\prime}_{3k+1})=f(u^{\prime}_{3k+2})=f(u_{n})=f(u^{\prime}_{n-1})=2$,
$f(u^{\prime}_{3k+3})=f(u_{n-1})=f(u^{\prime}_{n})=1$ for
$k=0,\ldots,\lfloor\frac{n}{3}\rfloor-1$ and $f(u_{i})=f(u^{\prime}_{i})=0$
otherwise. It is clear that $f$ is a RDRD-function of $C_{n}\odot K_{1}$ with
$f(V)=\frac{n-2}{3}\times 7+6=\frac{7n+4}{3}=\lceil\frac{7n}{3}\rceil+1$, thus
$\gamma_{rdR}(C_{n}\odot K_{1})\leq\lceil\frac{7n}{3}\rceil+1$.

Now we prove the inverse inequality. Since $\gamma_{rdR}(G)\geq\gamma_{dR}(G)$
for any graph $G$, and the known result in Theorem 5.4, we can obtain that
$\gamma_{rdR}(C_{n}\odot K_{1})\geq\lceil\frac{7n}{3}\rceil$. Thus
$\gamma_{rdR}(C_{n}\odot K_{1})=\lceil\frac{7n}{3}\rceil$ for $n\equiv
0,1(\bmod\ 3)$ can be obtained. We claim that $\gamma_{rdR}(C_{n}\odot
K_{1})\geq\lceil\frac{7n}{3}\rceil+1$ for $n\equiv 2(\bmod\ 3)$. Let $f$ be a
$\gamma_{rdR}(C_{n}\odot K_{1})$-function.

######  Claim 5.1.

For $C_{n}\odot K_{1}$, if there exists a $j$ such that
$f_{j}+f_{j+1}+f_{j+2}\geq 9$, then $\gamma_{rdR}(C_{n}\odot
K_{1})\geq\lceil\frac{7n}{3}\rceil+1$ for $n\equiv 2(\bmod\ 3)$.

###### Proof.

If there exists a $j_{1}$ such that $f_{j_{1}}+f_{j_{1}+1}+f_{j_{1}+2}\geq 9$,
then

$\displaystyle 3f(V)$
$\displaystyle=3\sum\nolimits_{j=1}^{n}f_{j}=(f_{j_{1}}+f_{j_{1}+1}+f_{j_{1}+2})+\sum\nolimits_{j\in\\{1,\ldots,n\\}-\\{j_{1}\\}}(f_{j}+f_{j+1}+f_{j+2})$
$\displaystyle\geq 9+7\times(n-1)$ $\displaystyle=7n+2.$

Thus $\gamma_{rdR}(C_{n}\odot
K_{1})\geq\frac{7n+2}{3}=\lceil\frac{7n}{3}\rceil+1$ for $n\equiv 2(\bmod\
3)$. ∎

By Claim 5.1, we may assume that $f_{j}+f_{j+1}+f_{j+2}\leq 8$ for all
$j$$(1\leq j\leq n)$, where subscripts are taken modulo $n$, for otherwise the
desired result follows. Recall Lemma 5.5, $7\leq f_{j}+f_{j+1}+f_{j+2}\leq 8$
for all $j$.

######  Claim 5.2.

For $C_{n}\odot K_{1}$, let $S=\\{j\colon f_{j}+f_{j+1}+f_{j+2}=8\\}$, there
must be $|S|\geq 2$ for $n\equiv 2(\bmod\ 3)$.

###### Proof.

Suppose $|S|=0$, it means that $f_{j}+f_{j+1}+f_{j+2}=7$ for all $j$. In this
case, $(f_{j},f_{j+1},f_{j+2})\in\\{(2,2,3),(2,3,2),(3,2,2)\\}$. Without loss
of generality, assume $f_{1}=3$. It follows $f_{2}=f_{3}=2$, $f_{4}=3$.
Continue in this way, we have $f(u_{3k+1})=f(u^{\prime}_{3k+2})=2$,
$f(u^{\prime}_{3k+1})=1$ for $k=0,\ldots,\lfloor\frac{n}{3}\rfloor$,
$f(u^{\prime}_{3k+3})=2$ for $k=0,\ldots,\lfloor\frac{n}{3}\rfloor-1$ and
$f(u_{i})=f(u^{\prime}_{i})=0$ otherwise. Note that $f(u_{n})=0$ and
$N(u_{n})\cap V_{0}=\emptyset$, which contradicts the definition of RDRD-
function. Suppose $|S|=1$, say $j_{1}\in S$. In this case, for any
$\gamma_{rdR}$-function,
$(f_{j_{1}},f_{{j_{1}}+1},f_{{j_{1}}+2})\in\\{(2,3,3),(3,3,2),(3,2,3)\\}$. If
$(f_{j_{1}},f_{{j_{1}}+1},f_{{j_{1}}+2})\in\\{(2,3,3),(3,3,2)\\}$, then
$({j_{1}}+1)\in S$ or $({j_{1}}-1)\in S$, that is there must be more
$j^{\prime}$ belongs to $S$. This is a contradiction to $|S|=1$. If
$(f_{j_{1}},f_{{j_{1}}+1},f_{{j_{1}}+2})=(3,2,3)$, then $f(u_{j_{1}+1})=0$ and
$f(u^{\prime}_{j_{1}+1})=2$. There must be a neighbor of $u_{j_{1}+1}$
assigned 0 by the RDRD function, say $f(u_{j_{1}+2})=0$. It follows
$f(u^{\prime}_{j_{1}+2})=3$. Since $|S|=1$, $f_{j_{1}+3}=f_{j_{1}+4}=2$. Note
that $f(u_{{j_{1}}+3})=0$ and $u_{{j_{1}+3}}$ cannot be dominated. This is a
contradiction. ∎

Thus for $n\equiv 2(\bmod\ 3)$, there are at least two columns $j_{1},j_{2}$
belong to the $S$ defined in Claim 5.2.

$\displaystyle 3f(V)$
$\displaystyle=3\sum\nolimits_{j=1}^{n}f_{j}=\sum\nolimits_{j\in\\{j_{1},j_{2}\\}}(f_{j}+f_{j+1}+f_{j+2})+\sum\nolimits_{j\in\\{1,\ldots,n\\}-\\{j_{1},j_{2}\\}}(f_{j}+f_{j+1}+f_{j+2})$
$\displaystyle\geq 8+8+7\times(n-2)$ $\displaystyle=7n+2.$

Thus $\gamma_{rdR}(C_{n}\odot
K_{1})\geq\frac{7n+2}{3}=\lceil\frac{7n}{3}\rceil+1$ for $n\equiv 2(\bmod\
3)$. ∎

######  Theorem 5.7.

${\gamma_{rdR}(P_{n}\odot
K_{1})=\left\\{\begin{array}[]{llll}\vspace{0.1cm}\lceil\frac{7n}{3}\rceil,&if\hskip
5.69054ptn\equiv 1(\bmod 3),\\\ \lceil\frac{7n}{3}\rceil+1,&if\hskip
5.69054ptn\equiv 0,2(\bmod 3).\end{array}\right.}$

###### Proof.

Figure 5.2 shows the graph of $P_{n}\odot K_{1}$.

Figure 5.2: Graph $P_{n}\odot K_{1}$.

Case 1. $n\equiv 0(\bmod\ 3)$. Define $f:V(P_{n}\odot
K_{1})\rightarrow\\{0,1,2,3\\}$ by $f(u_{3k+1})=f(u^{\prime}_{3k+2})=2$,
$f(u^{\prime}_{3k+1})=1$ for $k=0,\ldots,\frac{n}{3}-1$,
$f(u^{\prime}_{3k+3})=2$ for $k=0,\ldots,\frac{n}{3}-2$, $f(u^{\prime}_{n})=3$
and $f(u_{i})=f(u^{\prime}_{i})=0$ otherwise. It is clear that $f$ is a RDRD-
function of $P_{n}\odot K_{1}$ with $f(V)=\frac{n-3}{3}\times
7+8=\frac{7n+3}{3}=\frac{7n}{3}+1$, thus $\gamma_{rdR}(P_{n}\odot
K_{1})\leq\frac{7n}{3}+1$.

Case 2. $n\equiv 1(\bmod\ 3)$. Define $f:V(P_{n}\odot
K_{1})\rightarrow\\{0,1,2,3\\}$ by $f(u_{3k+1})=2$, $f(u^{\prime}_{3k+1})=1$
for $k=0,\ldots,\lfloor\frac{n}{3}\rfloor$,
$f(u^{\prime}_{3k+2})=f(u^{\prime}_{3k+3})=2$ for
$k=0,\ldots,\lfloor\frac{n}{3}\rfloor-1$ and $f(u_{i})=f(u^{\prime}_{i})=0$
otherwise. It is clear that $f$ is a RDRD-function of $P_{n}\odot K_{1}$ with
$f(V)=\frac{n-1}{3}\times 7+3=\frac{7n+2}{3}=\lceil\frac{7n}{3}\rceil$, thus
$\gamma_{rdR}(P_{n}\odot K_{1})\leq\lceil\frac{7n}{3}\rceil$.

Case 3. $n\equiv 2(\bmod\ 3)$. Define $f:V(P_{n}\odot
K_{1})\rightarrow\\{0,1,2,3\\}$ by $f(u_{3k+1})=f(u^{\prime}_{3k+2})=2$,
$f(u^{\prime}_{3k+1})=1$ for $k=0,\ldots,\lfloor\frac{n}{3}\rfloor$,
$f(u^{\prime}_{3k+3})=2$ for $k=0,\ldots,\lfloor\frac{n}{3}\rfloor-1$,
$f(u_{n})=1$ and $f(u_{i})=f(u^{\prime}_{i})=0$ otherwise. It is clear that
$f$ is a RDRD-function of $P_{n}\odot K_{1}$ with $f(V)=\frac{n-2}{3}\times
7+6=\frac{7n+4}{3}=\lceil\frac{7n}{3}\rceil+1$, thus $\gamma_{rdR}(P_{n}\odot
K_{1})\leq\lceil\frac{7n}{3}\rceil+1$.

Now we prove the inverse inequality. Since $\gamma_{rdR}(P_{n}\odot
K_{1})\geq\gamma_{rdR}(C_{n}\odot K_{1})$ and Theorem 5.6, we can obtain that
$\gamma_{rdR}(P_{n}\odot K_{1})\geq\lceil\frac{7n}{3}\rceil$ for $n\equiv
0,1(\bmod\ 3)$ and $\gamma_{rdR}(P_{n}\odot
K_{1})\geq\lceil\frac{7n}{3}\rceil+1$ for $n\equiv 2(\bmod\ 3)$. Thus the
results in Theorem 5.7 are true for $n\equiv 1,2(\bmod\ 3)$. Now we claim that
$\gamma_{rdR}(P_{n}\odot K_{1})\geq\frac{7n}{3}+1$ for $n\equiv 0(\bmod\ 3)$.
Let $f$ be a $\gamma_{rdR}(P_{n}\odot K_{1})$-function. By Lemma 5.5, for
$P_{n}\odot K_{1}$, $f_{j}+f_{j+1}+f_{j+2}\geq 7$, where $1\leq j\leq n-2$. In
particular, $f_{3k+1}+f_{3k+2}+f_{3k+3}\geq 7$, where $0\leq
k\leq\frac{n}{3}-1$. Suppose $\gamma_{rdR}(P_{n}\odot K_{1})=\frac{7n}{3}$, it
means that $f_{3k+1}+f_{3k+2}+f_{3k+3}=7$ for $0\leq k\leq\frac{n}{3}-1$. Note
that $f_{1}\geq 3$, the only possible case is
$f_{3k+1}=3,f_{3k+2}=f_{3k+3}=2$$(0\leq k\leq\frac{n}{3}-1)$. Note that
$f_{n}=2$ and $f(u_{n})=0$, $u_{n}$ cannot be restrained double Roman
dominated, which contradicts the definition of RDRD-function. Thus
$\gamma_{rdR}(P_{n}\odot K_{1})\geq\frac{7n}{3}+1$ for $n\equiv 0(\bmod\ 3)$.
∎

The following are some results of double Roman domination number on the corona
operation presented in [19]. Here we study the impact of corona operation on
restrained double Roman domination number.

######  Theorem 5.8.

[19]

${\gamma_{dR}(K_{p,q}\odot
K_{1})=\left\\{\begin{array}[]{llll}2(p+q)+1,&if\hskip 12.51918ptp=1\ or\
q=1,\\\ 2(p+q+1),&otherwise.\end{array}\right.}$

######  Theorem 5.9.

[19] For any graph $G$, $\gamma_{dR}((G\odot K_{1})\odot K_{1})=5n$, where
$n=|V(G)|$.

######  Proposition 5.10.

${\gamma_{rdR}(K_{p,q}\odot
K_{1})=\left\\{\begin{array}[]{llll}3(p+q),&if\hskip 12.51918ptp=1\ or\
q=1,\\\ 2(p+q+1),&otherwise.\end{array}\right.}$

###### Proof.

Let $\\{u_{1},\ldots,u_{p},v_{1},\ldots,v_{q}\\}$ be the vertex of
$V(K_{p,q})$. Let ${u^{\prime}_{i}}$ and ${v^{\prime}_{j}}$ be the leaf
neighbors of $u_{i}$ and $v_{j}$ respectively in $K_{p,q}\odot K_{1}$, where
$i\in\\{1,\ldots,p\\}$ and $j\in\\{1,\ldots,q\\}$.

Case 1. $p=1$ or $q=1$. Without loss of generality, assume $p=1$. Note that
$K_{1,q}\odot K_{1}$ is a wounded spider $ws(1,q,q-1)$ obtained from
subdividing $q-1$ edges of a star $K_{1,q}$. We refer to the result concerning
$\gamma_{rdR}(T)$ in [13], it implying that if $T$ is a wounded spider
$ws(1,q,q-1)$ with order $n$, then
$\gamma_{rdR}(ws(1,q,q-1))=\lceil\frac{3n-1}{2}\rceil$. That is
$\gamma_{rdR}(ws(1,q,q-1))=3(p+q)$ since $n=2(p+q)$ in $K_{1,q}\odot K_{1}$.

Case 2. $p,q\geq 2$. We define a function RDRD function $f$ with weight
$2(p+q+1)$ as follows.

${f(u)=\left\\{\begin{array}[]{llll}2,&if\hskip 4.55244ptu=u_{1}\ or\ u=v_{1}\
or\ u={u^{\prime}_{i}}(i\neq 1)\ or\ u={u^{\prime}_{j}}(j\neq 1),\\\
1,&if\hskip 4.55244ptu={u^{\prime}_{1}}\ or\ u={v^{\prime}_{1}},\\\
0,&otherwise.\end{array}\right.}$

Thus $\gamma_{rdR}(K_{p,q}\odot K_{1})\leq 2(p+q+1)$.

Recall the result in Theorem 5.8, that is $\gamma_{dR}(K_{p,q}\odot
K_{1})=2(p+q+1)$ for $p,q\geq 2$. Thus $\gamma_{rdR}(K_{p,q}\odot
K_{1})\geq\gamma_{dR}(K_{p,q}\odot K_{1})=2(p+q+1)$.

The result is true. ∎

Combining the above theorems, we present the bounds in Theorem 5.2 are sharp.
If $G\in\\{K_{n}(n\neq 2),C_{3},K_{1}\\}$, then the lower bound $2n+1$ of
$\gamma_{rdR}(G\odot K_{1})$ is arrived, where $n=|V(G)|$; if
$G\in\\{K_{p,q}(p=1\ or\ q=1),K_{1},K_{2}\\}$, the upper bound $3n$ of
$\gamma_{rdR}(G\odot K_{1})$ is arrived, where $n=|V(G)|$.

######  Theorem 5.11.

For any graph $G$, $\gamma_{rdR}((G\odot K_{1})\odot K_{1})=5n$, where
$n=|V(G)|$.

###### Proof.

Let $u_{i}\in V(G)$ for $i\in\\{1,\ldots,n\\}$, $v_{i}$ be the neighbor of
$u_{i}$ in $G\odot K_{1}$. Let ${u^{\prime}_{i}}$ and ${v^{\prime}_{i}}$ be
the leaf neighbors of $u_{i}$ and $v_{i}$ respectively in $(G\odot K_{1})\odot
K_{1}$. Now we define a function RDRD function $f$ with weight $5n$ as
follows, where $n=|V(G)|$.

${f(u)=\left\\{\begin{array}[]{llll}2,&if\hskip 4.55244ptu={u^{\prime}_{i}}\
or\ u={v_{i}},\hskip 3.98337ptwhere\hskip 3.98337pti\in\\{1,\ldots,n\\},\\\
1,&if\hskip 4.55244ptu={v^{\prime}_{i}}\hskip 3.98337ptwhere\hskip
3.98337pti\in\\{1,\ldots,n\\},\\\ 0,&otherwise.\end{array}\right.}$

Thus $\gamma_{rdR}((G\odot K_{1})\odot K_{1})\leq 5n$.

Recall the result in Theorem 5.8, that is $\gamma_{dR}((G\odot K_{1})\odot
K_{1})=5n$, where $n=|V(G)|$. Thus $\gamma_{rdR}((G\odot K_{1})\odot
K_{1})\geq\gamma_{dR}((G\odot K_{1})\odot K_{1})=5n$. ∎

## References

  * [1] H. A. Ahangar, M. Chellali and S. M. Sheikholeslami, On the double Roman domination in graphs, Discrte Appl. Math., 232(2017), 1-7.
  * [2] R. A. Beeler, T. W. Haynes and S. T. Hedetniemi, Double Roman domination, Discrete Appl. Math., 211(2016), 23-29.
  * [3] X. Chen, J. Liu and J. X. Meng, Total restrained domination in graphs, Comput. Math. Appl., 62(2011), 2892-2898.
  * [4] R. Chérifi, S. Gravier, X. Lagraula, C. Payan and I. Zighem, Domination number of the cross product of paths, Discrete Appl. Math., 94(1999), 101-139.
  * [5] G. S. Domke, J. H. Hattingh, S. T. Hedetniemi, R. C. Laskar and L. R. Markus, Restrained domination in graphs, Discrete Math., 203,1-3(1999), 61-69.
  * [6] W. Imrich and S. Klavžar. Product Graphs: structure and recognition. Wiley-Interscience, NewYork, USA, 2000.
  * [7] P. K. Jha, Perfect $r$-domination in the Kronecker product of two cycles, with an application to diagonal/toroidal mesh, Inform. Process. Lett., 87(3)(2003), 163-168.
  * [8] S. Klavžar and B. Zmazek, On a Vizing-like conjecture for direct product graphs, Discrete Math., 156(1996), 243-246.
  * [9] A. Klobučar, Domination numbers of cardinal products, Math. Slovaca., 49(4)(1999), 387-402.
  * [10] A. Klobučar, Domination numbers of cardinal products $P_{6}\times P_{n}$, Math. Commun., 4(1999), 241-250.
  * [11] A. Klobučar and A. Klobučar, Properties of double Roman domination on cardinal products of graphs, Ars Math. Contemp., 9(2)(2020), 337-349.
  * [12] A. C. Martínez, D. Kuziak, I. Peterin and I. G. Yero, Dominating the direct product of two graphs through total Roman strategies, Mathematics, 8(9)2020, 1438.
  * [13] D. A. Mojdeha, I. Masoumib and L. Volkmann, Restrained double Roman domination of a graph, [arXiv:2106.08501].
  * [14] P. R. L. Pushpam and C. Suseendran, Secure restrained domination in Graphs, Math. Comput. Sci., 9(2015), 239-247.
  * [15] P. R. L. Pushpam and S. Padmapriea, Restrained Roman domination in graphs, Transactions on Combinatorics, 4(1)(2015), 1-17.
  * [16] N. J. Rad and M. Krzywkowski, On the restrained Roman domination in graphs, In Colourings, Independence and Domination-CID 2015, University of Zielona Gora.
  * [17] B. Samadi, M. Alishahi, I. Masoumi and D. A. Mojdeh, Restrained Italian domination in graphs, RAIRO-Oper. Res., 55(2021), 319-332.
  * [18] B. Samadi, N. Soltankhah and D. A. Mojdeh, Restrained condition on double Roman dominating functions, arXiv:2109.066666v1.
  * [19] V. Anu and S. A. Lakshmanan, Impact of some graph operations on double Roman domination number, arXiv:1908.06859.
  * [20] V. G. Vizing, The Cartesian product of graphs. Vyčisl. Sistemy, 9(1963), 30-43.
  * [21] L. Volkmann, Double Roman domination and domatic numbers of graphs, Commun. Comb. Optim., 3(2018), 71-77.
  * [22] D. B. West, Introduction to graph theory, Upper Saddle River, NJ:Prentice Hall,1996.
  * [23] C. Q. Xi and J. Yue, The restrained double Roman domination of graphs, submitted.
  * [24] I. G. Yero and J. A. Rodríguez-Velázquez. Roman domination in Cartesian product graphs and strong product graphs, Appl. Anal. Discrete Math., 7(2)2013, 262-274.