On the Italian reinforcement number of a digraph

1.   Introduction

For notation and graph theory terminology, we in general follow ^[10] and ^[11]. Specifically, let $ D $ be a finite and simple digraph with vertex set $ V(D) $ and arc set $ A(D) $. For two vertices $ x, y\in V(D) $, we use $ (x, y) $ to denote the arc with direction from $ x $ to $ y $, that is, $ x $ is incident to $ (x, y) $ and $ y $ is incident from $ (x, y) $, and we also say $ x $ is an in-neighbor of $ y $ and $ y $ is an out-neighbor of $ x $. For $ v\in V(D) $, the out-neighborhood and in-neighborhood of $ v $, denoted by $ N^+_D(v) = N^+(v) $ and $ N^-_D(v) = N^-(v) $, are the sets of out-neighbors and in-neighbors of $ v $, respectively. Likewise, $ N_D^+[v] = N^+[v] = N^+(v)\cup \{v\} $ and $ N_D^-[v] = N^-[v] = N^-(v)\cup \{v\} $. In general, for a set $ X\subseteq V(D) $, we denote $ N^+_D(X) = N^+(X) = \bigcup_{v\in X}N^+(v) $. We write $ d^+_D(v) = d^+(v) = |N^+(v)| $ for the out-degree of a vertex $ v $ and $ d^-_D(v) = d^-(v) = |N^-(v)| $ for its in-degree. The maximum out-degree of $ D $ is denoted by $ \Delta^+(D) = \Delta^+ $. Let $ D_1 = (V_1, A_1) $ and $ D_2 = (V_2, A_2) $ be two digraphs. The Cartesian product of $ D_1 $ and $ D_2 $ is the digraph $ D_1\square D_2 $ with vertex set $ V_1\times V_2 $ and for $ (x_1, y_1), (x_2, y_2)\in V(D_1\square D_2) $, $ ((x_1, y_1), (x_2, y_2))\in A(D_1\square D_2) $ if and only if either $ (x_1, x_2)\in A_1 $ and $ y_1 = y_2 $, or $ x_1 = x_2 $ and $ (y_1, y_2)\in A_2 $.

A directed star is a digraph of order $ n\ge2 $ with vertex set $ \{u_1, u_2, \dots, u_{n}\} $ and arc set $ \{(u_1, u_i):2\le i\le n\} $. We call the center of a directed star to be a vertex of maximum out-degree. A leaf of a digraph $ D $ is a vertex of out-degree $ 0 $ and in-degree $ 1 $. For a vertex $ v \in X\subseteq V(D) $, the private neighborhood pn$ (v, X) $ of $ v $ is defined by pn$ (v, X) = N^+(v)\backslash N^+(X\backslash\{v\}) $. The complement of a digraph $ D $ denoted by $ \overline{D} $ is the digraph with vertex set $ V(D) $ defined by $ (u, v)\in A(\overline{D}) $ if and only if $ (u, v)\notin A(D) $. An oriented tree is a digraph that can be obtained from a tree by assigning a direction to (that is, orienting) each edge of the tree. We write $ C_n $ for the directed cycle of length $ n $, $ P_n $ for the directed path of order $ n $. For a real-valued function $ f:V(D)\rightarrow \mathbb{R} $, the weight of $ f $ is $ \omega(f) = \sum_{x\in V(D)}f(x) $, and for $ X\subseteq V(D) $, we define $ f(X) = \sum_{x\in X}f(x) $, and hence $ \omega(f) = f(V(D)) $.

Let $ G $ be a finite, simple and undirected graph with vertex set $ V(G) $ and edge set $ E(G) $. A function $ f:V(G)\rightarrow \{0, 1, 2\} $ is an Italian dominating function (IDF) on $ G $ if each vertex $ v\in V(G) $ assigned $ 0 $ under $ f $ satisfies $ \sum_{x\in N(v)}f(x)\ge2 $, where $ N(v) = \{x\in V(G): vx\in E(G)\} $. The minimum value of $ \sum_{x\in V(G)}f(x) $ of an IDF $ f $ on $ G $ is called the Italian domination number of $ G $. The Italian domination was introduced in ^[2] and has been studied by several authors ^{[1,6,7,12,13,14,17]}. For more details on Italian domination, we refer the reader to the recent book chapter ^[5] and survey paper ^[3].

A function $ f:V(D)\rightarrow \{0, 1, 2\} $ is an Italian dominating function (IDF) on a digraph $ D $ if each vertex $ v\in V(D) $ assigned $ 0 $ under $ f $ satisfies $ \sum_{x\in N^-(v)}f(x)\ge2 $. The minimum weight of an IDF on $ D $ is called the Italian domination number of $ D $ and is denoted by $ \gamma_{I}(D) $. And we say that a function $ f $ is a $ \gamma_{I}(D) $-function if it is an IDF with weight $ \gamma_{I}(D) $. Hao et al. ^[8] and Volkmann ^[18] independently introduced the concept of Italian domination in digraphs. This parameter has been studied in ^[16,19]. For more details on Roman domination parameters in digraphs, we refer the reader to ^[4].

Let $ \overline{G} $ be the complement of an undirected graph $ G $. A subset $ F $ of $ E(\overline{G}) $ is an Italian reinforcement set (IR-set) of $ G $ if $ \gamma_{I}(G+F)\le\gamma_{I}(G)-1 $. The Italian reinforcement number of a graph $ G $ is the minimum size of an IR-set of $ G $. In ^[9], Hao et al. introduced this concept.

Following the ideas in ^[9], Kim ^[15] initiated the study of Italian reinforcement number in digraphs. For a digraph $ D $, a subset $ F $ of $ A(\overline{D}) $ is an Italian reinforcement set (IR-set) of $ D $ if $ \gamma_{I}(D+F)\le\gamma_{I}(D)-1 $. The Italian reinforcement number of a digraph $ D $, denoted by $ r_I(D) $, is the minimum size of an IR-set of $ D $. An $ r_I(D) $-set is an IR-set $ F $ of $ D $ with $ |F| = r_I(D) $. It is clear that if $ 1\le \gamma_{I}(D)\le2 $, then addition of arcs does not reduce the Italian domination number. Thus if $ 1\le \gamma_{I}(D)\le2 $, then the Italian reinforcement number is defined to be 0. Consequently we always assume that when we discuss $ r_I(D) $, all digraphs involved satisfy $ \gamma_{I}(D)\ge3 $.

For an IDF $ f $ on $ D $, let $ V_i = \{v\in V(D):f(v) = i\} $ for $ i\in\{0, 1, 2\} $ and hence $ f $ can be represented by the ordered triple $ (V_0, V_1, V_2) $ (or $ (V^f_0, V^f_1, V^f_2) $ to refer $ f $) of $ V(D) $ induced by $ f $.

The aim of this paper is to continue the study of Italian reinforcement number in digraphs. We establish some new sharp upper bounds on the Italian reinforcement number. Also, we determine the exact values of $ r_I(P_2\square P_n) $, $ r_I(P_3\square P_n) $, $ r_I(P_3\square C_n) $, $ r_I(C_3\square P_n) $ and $ r_I(C_3\square C_n) $.

2.   Preliminaries

In this section, some fundamental results that are used in this paper are herein recalled. The reader is referred to ^[15] for more information and details.

Proposition A. Let $ D $ be a digraph with $ \gamma_{I}(D)\ge3 $, $ F $ be an $ r_I(D) $-set and let $ f $ be a $ \gamma_I(D+F) $-function. Then

$(a)$ For each arc $ (u, v)\in F $, $ f(u)\in\{1, 2\} $ and $ f(v) = 0 $.

$ (b) $ $ \gamma_I(D+F) = \gamma_I(D)-1 $.

Proposition B. Let $ D $ be a digraph with $ \gamma_{I}(D)\ge3 $. Then $ r_{I}(D) = 1 $ if and only if there exist a $ \gamma_I(D) $-function $ f = (V_0, V_1, V_2) $ and a vertex $ v\in V_1 $ such that one of the following conditions holds:

$ (a) $ $ f(N_D^-(v)) = 0 $, $ f(N_D^-(x)\backslash\{v\})\ge2 $ for each $ x\in N_D^+(v)\cap V_0 $ and $ V_2\ne\emptyset $.

$ (b) $ $ f(N_D^-(v)) = 1 $ and $ f(N_D^-(x)\backslash\{v\})\ge2 $ for each $ x\in N_D^+(v)\cap V_0 $.

Proposition C. For any digraph $ D $ of order $ n $ with $ \gamma_{I}(D)\ge3 $,

Proposition D. If $ D $ is a digraph of order $ n\ge 3 $ with $ \Delta^+(D) \ge 1 $ and $ \gamma_I(D) = n $, then $ r_I(D) = 1 $.

Hao et al. ^[8] showed that for any integer $ n\ge3 $, $ \gamma_I(P_n) = \gamma_I(C_n) = n $, which, together with Proposition D, would yield the following result directly.

Corollary 2.1. For any integer $ n\ge3 $, $ r_{I}(P_n) = r_{I}(C_n) = 1 $.

3.   Upper bounds on $ r_{I}(D) $

Our aim in this section is to derive some sharp upper bounds for Italian reinforcement number in digraphs.

Proposition 3.1. Let $ D $ be a digraph and let $ H $ be a subdigraph of $ D $ with $ \gamma_I(H) = \gamma_I(D)\ge3 $. Then $ r_I(D)\le r_I(H) $.

Proof. Let $ F $ be an $ r_I(H) $-set. Since $ H+F $ is a subdigraph of $ D+(F\backslash A(D)) $, we conclude from Proposition A(b) that

This implies that $ F\backslash A(D) $ is an IR-set of $ D $ and so $ r_I(D)\le|F\backslash A(D)|\le|F| = r_I(H) $, as desired.

Note that $ P_n $ is a subdigraph of $ C_n $ and $ \gamma_I(P_n) = \gamma_I(C_n) = n $ for $ n\ge 3 $. Moreover, it follows from Corollary 2.1 that $ r_{I}(P_n) = r_{I}(C_n) = 1 $. This demonstrates the sharpness of Proposition 3.1.

Theorem 3.2. For any digraph $ D $ with $ \gamma_{I}(D)\ge3 $, let $ f = (V_0, V_1, V_2) $ be a $ \gamma_I(D) $-function. Then

$(a) $ If $ v\in V_1 $, then $ r_{I}(D)\le |(N^+(v)\backslash pn(v, V_1))\cap V_0|+2 $.

$ (b) $ If $ v\in V_2 $, then $ r_{I}(D)\le |pn(v, V_2)\cap V_0| $.

Proof. $ (a) $ Let $ v\in V_1 $. First, assume that $ V_2\ne\emptyset $. Let $ w\in V_2 $ and let $ F = (\{(w, x):x\in (N^+(v)\backslash pn(v, V_1))\cap V_0\}\cup\{(w, v)\})\backslash A(D) $. Note that every vertex in $ pn(v, V_1)\cap V_0 $ has at least one in-neighbor in $ V_2 $. Thus the function $ h_1 $ defined by $ h_1(v) = 0 $ and $ h_1(x) = f(x) $ for each $ x\in V(D)\backslash \{v\} $ is an IDF on $ D+F $ with $ \omega(h_1) = \omega(f)-1 $ and hence $ F $ is an IR-set of $ D $, implying that

Second, assume that $ V_2 = \emptyset $. This forces $ pn(v, V_1)\cap V_0 = \emptyset $. Note that there must exist two distinct vertices $ v_1, v_2\in V_1\backslash \{v\} $ since $ \gamma_{I}(D)\ge3 $. Let $ U_1 = N^+(v)\cap N^+(v_1)\cap V_0 $, $ U_2 = (N^+(v)\backslash N^+(v_1))\cap V_0 $ and let $ F = (\{(v_1, v), (v_2, v)\}\cup\{(v_2, x):x\in U_1\}\cup\{(v_1, x):x\in U_2\})\backslash A(D) $. One can check that the function $ h_1 $ defined earlier is an IDF on $ D+F $ with $ \omega(h_1) = \omega(f)-1 $ and hence $ F $ is an IR-set of $ D $, implying that

where the last '$ = $' holds since $ pn(v, V_1)\cap V_0 = \emptyset $.

As a result, $ (a) $ is true.

$ (b) $ Let $ v\in V_2 $. Then there must exist a vertex $ w\in V_1\cup V_2 $ since $ \gamma_{I}(D)\ge3 $. Let $ F = \{(w, x):x\in pn(v, V_2)\cap V_0\}\backslash A(D) $. It is obvious that the function $ h_2 $ defined by $ h_2(v) = 1 $ and $ h_2(x) = f(x) $ for each $ x\in V(D)\backslash \{v\} $ is an IDF on $ D+F $ with $ \omega(h_2) = \omega(f)-1 $ and hence $ F $ is an IR-set of $ D $, implying that

as desired.

This completes the proof.

Remark 1. The upper bounds in Theorem 3.2 are sharp. To see this, consider the following two examples.

$ (a) $ Let $ D $ be the digraph with vertex set $ X\cup Y $, where $ X = \{x_i:1\le i\le 4\} $ and $ Y = \{y_i:1\le i\le 4\} $, and arc set $ \{(x_i, x_j), (y_i, y_j):1\le i\le 2, 3\le j\le 4\} $. One can check that the function $ f = (\{x_3, x_4, y_3, y_4\}, \{x_1, x_2, y_1, y_2\}, \emptyset) $ is a $ \gamma_{I}(D) $-function and hence $ \gamma_{I}(D) = 4 $.

We next prove that $ r_{I}(D)\ge4 $. Let $ F $ be an $ r_I(D) $-set and let $ g $ be a $ \gamma_I(D+F) $-function. We deduce from Proposition A$ (b) $ that $ \omega(g) = \gamma_I(D+F) = \gamma_I(D)-1 = 3 $. If $ g(X) = 0 $ (resp., $ g(Y) = 0 $), then every vertex of $ X $ (resp., $ Y $) is incident from one arc in $ F $ and so $ |F|\ge|X| = 4 $ (resp., $ |F|\ge|Y| = 4 $). So in the following we may assume that $ g(X)\ge1 $ and $ g(Y)\ge1 $. Recall that $ g(X)+g(Y) = \omega(g) = 3 $. By symmetry, assume that $ g(X) = 2 $ and $ g(Y) = 1 $.

First, assume that exactly one vertex of $ X $ is assigned $ 2 $ under $ g $ and the others are assigned $ 0 $ under $ g $. Without loss of generality, assume that $ g(x_2) = 0 $. Since $ d^-_D(x_2) = 0 $, $ x_2 $ is incident from one arc in $ F $. Moreover, since $ g(Y) = 1 $, each of exactly three vertices of $ Y $ assigned $ 0 $ under $ g $ is incident from at least one arc in $ F $. As a result, we have $ |F|\ge4 $.

Second, assume that exactly two vertices of $ X $ are assigned $ 1 $ under $ g $. This forces $ V_2^g = \emptyset $. Recall that $ g(Y) = 1 $. If $ g(y_1) = 1 $ (the case $ g(y_2) = 1 $ is similar), then $ g(y_2) = g(y_3) = g(y_4) = 0 $ and hence $ y_2 $ is incident from two arcs in $ F $ and each of $ y_3 $ and $ y_4 $ is incident from one arc in $ F $, implying that $ |F|\ge4 $. If $ g(y_3) = 1 $ (the case $ g(y_4) = 1 $ is similar), then $ g(y_1) = g(y_2) = 0 $ and hence each of $ y_1 $ and $ y_2 $ is incident from two arcs in $ F $, implying that $ |F|\ge4 $.

Therefore, the above arguments mean that $ r_{I}(D) = |F|\ge4 $. Now let $ F' = \{(x_1, y_2), (x_2, y_2), $ $ (x_1, y_{3}), (x_1, y_4)\} $. It is not difficult to verify that the function $ h = (\{x_3, x_4, y_2, y_3, y_4\}, \{x_1, x_2, y_1\}, $ $ \emptyset) $ is an IDF on $ D+F' $ with $ \omega(h) = 3 < \gamma_{I}(D) $ and hence $ F' $ is an IR-set of $ D $. Thus $ r_{I}(D)\le|F'| = 4 $. As a result, we obtain $ r_{I}(D) = 4 $.

Note that $ f = (\{x_3, x_4, y_3, y_4\}, \{x_1, x_2, y_1, y_2\}, \emptyset) $ is a $ \gamma_{I}(D) $-function. We have that for $ 1\le i\le2 $,

$ (b) $ Let $ t\ge s\ge3 $ and $ p\ge1 $ be arbitrary integers and let $ D $ be the digraph with vertex set $ \{u_i:1\le i\le s\}\cup\{v_i:1\le i\le t\}\cup\{w_i:1\le i\le p\} $ and arc set $ \{(u_1, u_i):2\le i\le s\}\cup\{(v_1, v_i):2\le i\le t\}\cup\{(u_1, w_i), (v_1, w_i):1\le i\le p\} $.

Let $ g_1 $ be a $ \gamma_{I}(D) $-function. If there exists some vertex in $ \{u_2, u_3, \dots, u_s\} $ assigned $ 0 $ under $ g_1 $, then $ g_1(u_1) = 2 $ and if each vertex in $ \{u_2, u_3, \dots, u_s\} $ is assigned $ 1 $ or $ 2 $ under $ g_1 $, then $ \sum_{i = 2}^sg_1(u_i)\ge s-1 $. In either case, we have $ \sum_{i = 1}^sg_1(u_i)\ge2 $. Similarly, we have $ \sum_{i = 1}^tg_1(v_i)\ge2 $. Therefore, $ \gamma_{I}(D)\ge4 $. On the other hand, the function $ f = (V(D)\backslash \{u_1, v_1\}, \emptyset, \{u_1, v_1\}) $ is an IDF on $ D $ and so $ \gamma_{I}(D)\le\omega(f) = 4 $. Consequently, we have $ \gamma_{I}(D) = 4 $. This also implies that the function $ f $ is a $ \gamma_{I}(D) $-function.

We next prove that $ r_{I}(D) = s-1 $. Let $ F' = \{(v_1, u_i):2\le i\le s\} $. Then the function $ g_2 $ defined by $ g_2(u_1) = 1 $, $ g_2(v_1) = 2 $ and $ g_2(x) = 0 $ otherwise, is an IDF on $ D+F' $ with $ \omega(g_2) = 3 < \gamma_{I}(D) $, and hence $ F' $ is an IR-set of $ D $. Thus $ r_{I}(D)\le|F'| = s-1 $. Therefore it is enough to prove that $ r_{I}(D)\ge s-1 $. Let $ F $ be an $ r_I(D) $-set and let $ h $ be a $ \gamma_I(D+F) $-function. We conclude from Proposition A$ (b) $ that $ \omega(h) = \gamma_I(D+F) = \gamma_I(D)-1 = 3 $. If $ \sum_{i = 1}^th(v_i)\in\{0, 1\} $, then at least $ t-1 $ vertices in $ \{v_1, v_2, \dots, v_t\} $ is incident from an arc in $ F $ and hence $ |F|\ge t-1\ge s-1 $. If $ \sum_{i = 1}^th(v_i)\in\{2, 3\} $, then this forces $ \sum_{i = 1}^sh(u_i)\in\{0, 1\} $ and hence at least $ s-1 $ vertices in $ \{u_1, u_2, \dots, u_s\} $ is incident from an arc in $ F $, implying that $ |F|\ge s-1 $. As a result, we obtain $ r_{I}(D) = s-1 $.

Note that the function $ f = (V(D)\backslash \{u_1, v_1\}, \emptyset, \{u_1, v_1\}) $ is a $ \gamma_{I}(D) $-function, $ |pn(u_1, V^f_2)\cap V_0^f| = s-1 $ and $ |pn(v_1, V^f_2)\cap V_0^f| = t-1 $. Thus if $ s = t $, then

As an immediate consequence of Theorem 3.2, we have the following result on the Italian reinforcement number of a digraph in terms of its maximum out-degree.

Corollary 3.3. For any digraph $ D $ with $ \gamma_{I}(D)\ge3 $, $ r_{I}(D)\le\Delta^++2. $

The example of (a) in Remark 1 demonstrates that Corollary 3.3 is sharp. Using Corollary 3.3 and Proposition C, we obtain the following result.

Corollary 3.4. Let $ D $ be a digraph of order $ n $ with $ \gamma_{I}(D)\ge3 $. Then $ r_{I}(D)\le \lceil n/2\rceil $.

Proof. If $ \Delta^+\le \lceil n/2\rceil-2 $, then it follows from Corollary 3.3 that $ r_{I}(D)\le\Delta^++2\le\lceil n/2\rceil $. If $ \Delta^+\ge \lceil n/2\rceil-1 $, then by Proposition C, we get

which completes our proof.

The upper bound of Corollary 3.4 is sharp. For example, let $ D $ be the digraph with vertex set $ \{u_i, v_i:0\le i\le 3\} $ and arc set $ \{(u_i, v_{i}), (u_i, v_{i+1}):0\le i\le 3\} $, where the indices are taken modulo $ 4 $. It is not difficult to check that the function $ f = (\{v_i: 0\le i\le 3\}, \{u_i: 0\le i\le 3\}, \emptyset) $ is the unique $ \gamma_{I}(D) $-function, the set $ F = \{(u_0, u_3), (u_1, u_3), (u_0, v_3), (u_1, v_0)\} $ is an $ r_I(D) $-set and $ g = (\{u_3\}\cup\{v_i: 0\le i\le 3\}, \{u_i: 0\le i\le 2\}, \emptyset) $ is a $ \gamma_{I}(D+F) $-function. Therefore $ r_{I}(D) = |F| = 4 $.

The upper bound of Corollary 3.3 can be improved if we restrict our attention to any digraph $ D $ with at least one leaf and $ \gamma_{I}(D)\ge3 $.

Theorem 3.5. For any digraph $ D $ with at least one leaf and $ \gamma_{I}(D)\ge3 $, $ r_{I}(D)\le\max\{2, \Delta^+\}. $

Proof. Let $ u $ be a leaf of $ D $, $ v $ be the unique in-neighbor of $ u $ and let $ f $ be a $ \gamma_I(D) $-function. Clearly $ f(u)\le1 $. If $ f(u) = 0 $, then this forces $ f(v) = 2 $ and it follows from Theorem 3.2$ (b) $ that

So in the following we may assume that $ f(u) = 1 $. It is not different to verify that $ f(v)\le1 $. Define the function $ g $ by $ g(u) = 0 $ and $ g(x) = f(x) $ for each $ x\in V(D)\backslash\{u\} $.

Assume first that $ f(v) = 1 $. Since $ \gamma_{I}(D)\ge3 $, there exists some vertex $ w\in V(D)\backslash\{u, v\} $ such that $ f(w)\ge1 $ and hence the function $ g $ defined earlier is an IDF on $ D+\{(w, u)\} $ with $ \omega(g) = \omega(f)-1 < \gamma_I(D) $, and so $ \{(w, u)\} $ is an IR-set of $ D $, implying that $ r_I(D) = 1 < \max\{2, \Delta^+\} $.

Assume next that $ f(v) = 0 $. Then $ f(N^-(v))\ge2 $. If there exists some vertex $ w\in N^-(v) $ such that $ f(w) = 2 $, then the function $ g $ defined earlier is an IDF on $ D+\{(w, u)\} $ with $ \omega(g) = \omega(f)-1 < \gamma_I(D) $, and so $ \{(w, u)\} $ is an IR-set of $ D $, implying that $ r_I(D) = 1 < \max\{2, \Delta^+\} $. If there exist two different vertices $ w_1, w_2\in N^-(v) $ such that $ f(w_1) = f(w_2) = 1 $, then the function $ g $ defined earlier is an IDF on $ D+\{(w_1, u), (w_2, u)\} $ with $ \omega(g) = \omega(f)-1 < \gamma_I(D) $, and so $ \{(w_1, u), (w_2, u)\} $ is an IR-set of $ D $, implying that $ r_I(D)\le2\le\max\{2, \Delta^+\} $.

This completes the proof.

It is worth pointing out that the upper bound of Theorem 3.5 is sharp. We shall construct infinitely many digraphs $ \mathcal{T} $ with $ r_{I}(\mathcal{T}) = \max\{2, \Delta^+(\mathcal{T})\}. $ Let $ \Delta\ge2 $ be an arbitrary integer and let $ T $ denote an oriented tree with $ 1\le\Delta^+(T)\le\Delta $. For any vertex $ u\in V(T) $, let $ S_u $ denote a directed star of order $ \Delta $ with center $ C(S_u) $. Define $ \mathcal{T}(\Delta, T) $ to be the digraph obtained from $ T\cup(\bigcup_{u\in V(T)}S_u) $ by adding a new arc $ (C(S_u), u) $ for each $ u\in V(T) $.

Proposition 3.6. For an arbitrary integer $ \Delta\ge2 $, let $ T $ be an oriented tree with $ 1\le\Delta^+(T)\le\Delta $ and let $ \mathcal{T} = \mathcal{T}(\Delta, T) $. Then $ r_{I}(\mathcal{T}) = \max\{2, \Delta^+(\mathcal{T})\} $.

Proof. We now claim that $ \gamma_I(\mathcal{T}) = 2|V(T)| $. It is easy to see that the function $ h_1 $ defined by $ h_1(C(S_u)) = 2 $ for each $ u\in V(T) $ and $ h_1(x) = 0 $ otherwise, is an IDF on $ \mathcal{T} $ and hence $ \gamma_I(\mathcal{T})\le\omega(h_1) = 2|V(T)| $. Thus it is enough for us to prove that $ \gamma_I(\mathcal{T})\ge2|V(T)| $. Let $ h_2 $ be a $ \gamma_I(\mathcal{T}) $-function. Noting that $ d^-_{\mathcal{T}}(C(S_u)) = 0 $ for each $ u\in V(T) $, we have $ h_2(C(S_u))\ge1 $ and hence if there exists a leaf $ x $ of $ S_u $ such that $ h_2(x)\ge1 $, then $ h_2(V(S_u))\ge h_2(C(S_u))+h_2(x)\ge2 $ and if there exists a leaf $ x $ of $ S_u $ such that $ h_2(x) = 0 $, then $ h_2(V(S_u))\ge h_2(C(S_u)) = 2 $. Consequently, we get

We next prove that $ r_{I}(\mathcal{T}) = \max\{2, \Delta^+(\mathcal{T})\} $. It follows from Theorem 3.5 that $ r_I(\mathcal{T})\le\max\{2, \Delta^+(\mathcal{T})\} $. Note that $ \max\{2, \Delta^+(\mathcal{T})\} = \Delta $. Thus it is enough for us to prove that $ r_{I}(\mathcal{T})\ge\Delta $. Let $ F $ be an $ r_I(\mathcal{T}) $-set and $ f $ be a $ \gamma_I(\mathcal{T}+F) $-function.

Claim 3.7. For any vertex $ u\in V(T) $ with $ f(V(S_u))\le1 $, there must exist a vertex in $ V(S_u) $ incident from an arc in $ F $.

Proof of Claim 3.7. Let $ u $ be any vertex of $ V(T) $ with $ f(V(S_u))\le1 $. Note that $ f(C(S_u))\le f(V(S_u))\le1 $. If $ f(C(S_u)) = 0 $, then $ C(S_u) $ is incident from an arc in $ F $ since $ d^-_{\mathcal{T}}(C(S_u)) = 0 $, and if $ f(C(S_u)) = 1 $, then $ f(V(S_u)\backslash\{C(S_u)\}) = 0 $ and hence each vertex of $ V(S_u)\backslash\{C(S_u)\} $ is incident from an arc in $ F $. Thus Claim 3.7 is true.

Claim 3.8. For any vertex $ u\in V(T) $ with $ f(V(S_u)\cup\{u\})\le1 $,

$ (a) $ There exist $ \Delta-1 $ vertices in $ V(S_u)\cup\{u\} $ incident from an arc in $ F $.

$ (b) $ If the number of vertices in $ V(S_u)\cup\{u\} $ incident from an arc in $ F $ is $ \Delta-1 $, then $ f(V(S_u)) = 1 $ and $ u $ is not adjacent from an arc in $ F $.

Proof of Claim 3.8. Let $ u $ be any vertex of $ V(T) $ with $ f(V(S_u)\cup\{u\})\le1 $. It is obvious that $ f(V(S_u))\le1 $. If $ f(V(S_u)) = 0 $, then each vertex of $ S_u $ is adjacent from an arc in $ F $, and if $ f(V(S_u)) = 1 $, then each of exactly $ \Delta-1 $ vertices of $ S_u $ assigned $ 0 $ under $ f $ is adjacent from an arc in $ F $. Thus Claim 3.8 is also true.

We deduce from Proposition A$ (b) $ that $ \gamma_I(\mathcal{T}+F) = \gamma_I(\mathcal{T})-1 = 2|V(T)|-1 $ and hence there exists a vertex $ u\in V(T) $ satisfying $ f(V(S_u)\cup\{u\})\le1 $. Moreover, if there exists a vertex $ v\in V(T)\backslash\{u\} $ satisfying $ f(V(S_{v})\cup\{v\})\le1 $, then we conclude from Claim 3.8$ (a) $ that $ |F|\ge2(\Delta-1)\ge\Delta $. So in the following we may assume that $ u $ is the unique vertex satisfying $ f(V(S_u)\cup\{u\})\le1 $. This implies that $ f(V(S_{w})\cup\{w\})\ge2 $ for each $ w\in V(T)\backslash\{u\} $.

If $ f(V(S_u)) = 0 $ or $ u $ is incident from an arc in $ F $, then we deduce from Claim 3.8 that $ r_{I}(\mathcal{T}) = |F|\ge\Delta $. Suppose, next, that $ f(V(S_u)) = 1 $ and $ u $ is not incident from an arc in $ F $. This forces $ f(V(S_u)\cup\{u\}) = 1 $ and $ f(u) = 0 $. Furthermore, since $ \omega(f) = \gamma_I(\mathcal{T}+F) = 2|V(T)|-1 $ and $ f(V(S_w)\cup\{w\})\ge2 $ for each $ w\in V(T)\backslash\{u\} $, one can verify that $ f(V(S_{w})\cup\{w\}) = 2 $. Since $ f(V(S_u)) = 1 $, $ f(u) = 0 $ and $ u $ is not incident from an arc in $ F $, there must exist an in-neighbor, say $ v $, of $ u $ in $ T $ with $ f(v)\ge1 $. Moreover, it is clear that $ f(V(S_{v})\cup\{v\}) = 2 $ since $ v\in V(T)\backslash\{u\} $ and hence $ f(V(S_{v})) = f(V(S_{v})\cup\{v\})-f(v)\le1 $. Thus it follows from Claim 3.7 that there must exist a vertex of $ V(S_v) $ incident from an arc in $ F $. Furthermore, since $ f(V(S_u)\cup\{u\}) = 1 $, Claim 3.8$ (a) $ yields that there exist $ \Delta-1 $ vertices in $ V(S_u)\cup\{u\} $ incident from an arc in $ F $. Therefore, we get $ r_{I}(\mathcal{T}) = |F|\ge\Delta $.

This completes the proof.

Let $ r $ be a positive integer and let $ n = 2r+1 $. We define the circulant tournament $ CT(n) $ of order $ n $ with vertex set $ \{u_0, u_1, \dots, u_{n-1}\} $ as follows. For each $ i\in \{0, 1, \dots, n-1\} $, the arcs are going from $ u_i $ to the vertices $ u_{i+1}, u_{i+2}, \dots, u_{i+r} $, where the indices are taken modulo $ n $. For Italian domination number, Hao et al. ^[8] showed the following result.

Proposition E. (^[8]) Let $ r $ be a positive integer and let $ n = 2r+1 $. Then

The following result, which can be deduced from Propositions C and E, indicates that the upper bound in Proposition C is sharp.

Proposition 3.9. Let $ r $ be a positive integer and let $ n = 2r+1 $. Then

Proof. If $ r = 1 $, that is, if $ CT(n) $ is a directed cycle of length $ 3 $, then Corollary 2.1 yields $ r_{I}(CT(n)) = 1 $. So in the following we may assume that $ r\ge2 $. By Propositions C and E, we have

Hence it suffices to prove that $ r_{I}(CT(n))\ge r-1 $. Let $ F $ be an $ r_I(CT(n)) $-set and let $ f = (V_0, V_1, V_2) $ be a $ \gamma_I(CT(n)+F) $-function. Then by Propositions A$ (b) $ and E, we have

This implies that $ |V_1| = |V_2| = 1 $, or $ |V_1| = 3 $ and $ |V_2| = 0 $.

Suppose now that $ |V_1| = |V_2| = 1 $. Without loss of generality, assume that $ u_0\in V_2 $ and $ u_{i_0}\in V_1 $ for some $ i_0\in \{1, 2, \dots, 2r\} $. Then for each $ j\in \{r+1, r+2, \dots, 2r\}\backslash\{i_0\} $, $ u_j\notin N^+_{CT(n)}(u_0) $ and hence by the definition of $ \gamma_I(CT(n)+F) $-function, we have $ u_j $ is adjacent from one arc in $ F $. Thus $ r_{I}(CT(n)) = |F|\ge r-1 $. Suppose next that $ |V_1| = 3 $ and $ |V_2| = 0 $. Without loss of generality, assume that $ u_0, u_k, u_l\in V_1 $ for $ 0 < k < l\le2r $.

First, assume that $ l-k < r $, where $ k, l\in\{1, 2, \dots, r\} $. Then $ N^-_{CT(n)}(u_j)\cap\{u_0, u_k, u_l\} = \{u_0\} $ for each $ j\in \{1, 2, \dots, k-1\} $, $ N^-_{CT(n)}(u_j)\cap\{u_0, u_k, u_l\} = \{u_l\} $ for each $ j\in \{k+r+1, k+r+2, \dots, l+r\} $ and $ N^-_{CT(n)}(u_j)\cap\{u_0, u_k, u_l\} = \emptyset $ for each $ j\in \{l+r+1, l+r+2, \dots, 2r\} $. This implies that $ r_{I}(CT(n)) = |F|\ge r-1 $.

Second, assume that $ l-k < r $, where $ k\in\{2, 3, \dots, r\} $ and $ l\in\{r+1, r+2, \dots, 2r-1\} $. Clearly $ N^-_{CT(n)}(u_j)\cap\{u_0, u_k, u_l\} = \{u_0\} $ for each $ j\in \{l-r, l-r+1, \dots, k-1\} $, $ N^-_{CT(n)}(u_j)\cap\{u_0, u_k, u_l\} = \{u_k\} $ for each $ j\in \{r+1, r+2, \dots, l-1\} $ and $ N^-_{CT(n)}(u_j)\cap\{u_0, u_k, u_l\} = \{u_l\} $ for each $ j\in \{k+r+1, k+r+2, \dots, 2r\} $. This implies that $ r_{I}(CT(n)) = |F|\ge r-1 $.

Third, assume that $ l-k < r $, where $ k, l\in\{r+1, r+2, \dots, 2r\} $. Clearly $ N^-_{CT(n)}(u_j)\cap\{u_0, u_k, u_l\} = \{u_0\} $ for each $ j\in \{l-r, l-r+1, \dots, r\} $, $ N^-_{CT(n)}(u_j)\cap\{u_0, u_k, u_l\} = \emptyset $ for each $ j\in \{r+1, r+2, \dots, k-1\} $ and $ N^-_{CT(n)}(u_j)\cap\{u_0, u_k, u_l\} = \{u_k\} $ for each $ j\in \{k+1, k+2, \dots, l-1\} $. This implies that $ r_{I}(CT(n)) = |F|\ge r-1 $.

Finally assume that $ l-k\ge r $. Then $ 1\le k\le r $ and $ r+1\le l\le 2r $. It is clear that $ N^-_{CT(n)}(u_j)\cap\{u_0, u_k, u_l\} = \{u_k\} $ for each $ j\in \{r+1, r+2, \dots, k+r\}\backslash\{l\} $, $ N^-_{CT(n)}(u_j)\cap\{u_0, u_k, u_l\} = \emptyset $ for each $ j\in \{k+r+1, k+r+2, \dots, l-1\} $ and $ N^-_{CT(n)}(u_j)\cap\{u_0, u_k, u_l\} = \{u_l\} $ for each $ j\in \{l+1, l+2, \dots, 2r\} $. This implies that $ r_{I}(CT(n)) = |F|\ge r-1 $.

This completes the proof.

4.   Exact values

In this section, we first determine the exact values of $ \gamma_I(P_2\square P_n) $, $ \gamma_I(P_3\square P_n) $, $ \gamma_I(P_3\square C_n) $ and $ \gamma_I(C_3\square P_n) $, based on which we further determine the exact values of Italian reinforcement number of some classes of cartesian products.

Let $ m\in\{2, 3\} $ and $ n\ge m $ be an integer. We emphasize that $ V(P_m\square P_n) = \{(i, j):1\le i\le m, 1\le j\le n\} $ and $ A(P_m\square P_n) = \{((i, j), (i+1, j)):1\le i\le m-1, 1\le j\le n\}\cup\{((i, j), (i, j+1)):1\le i\le m, 1\le j\le n-1\} $. For notational convenience, if $ f $ is an IDF on $ P_m\square P_n $, then we denote $ a_j = \sum_{i = 1}^mf((i, j)) $ for each $ 1\le j\leq n $.

Now we consider the exact value of Italian domination number of $ P_2\square P_n $. We begin with the following lemma.

Lemma 4.1. Let $ n\ge2 $ be an integer and let $ f $ be a $ \gamma_I(P_2\square P_n) $-function. Then $ a_1\ge2 $ and $ a_j\ge1 $ for each $ j\in\{2, 3, \ldots, n\} $.

Proof. Since $ d^-((1, 1)) = 0 $, we have $ f((1, 1))\ge1 $. If $ f((1, 1)) = 2 $, then $ a_1\ge f((1, 1)) = 2 $. If $ f((1, 1)) = 1 $, then clearly $ f((2, 1))\ge1 $ since $ (1, 1) $ is the unique in-neighbor of $ (2, 1) $ and so $ a_1 = f((1, 1))+f((2, 1))\ge2 $. We next show that $ a_j\ge1 $ for each $ j\in\{2, 3, \ldots, n\} $. Suppose, to the contrary, that there exists some $ j\in\{2, 3, \ldots, n\} $ such that $ a_j = f((1, j))+f((2, j)) = 0 $. Then by the definition of $ \gamma_{I}(P_2\square P_n) $-function, we have $ f((1, j-1)) = f((2, j-1)) = 2 $. One can check that the function $ g $ defined by $ g((2, j-1)) = 0 $, $ g((2, j)) = 1 $ and $ g(x) = f(x) $ otherwise, is an IDF on $ P_2\square P_n $ with $ \omega(g) = \omega(f)-1 < \gamma_I(P_2\square P_n) $, a contradiction. As a result, we obtain $ a_j\ge1 $ for each $ j\in\{2, 3, \ldots, n\} $.

Theorem 4.2. For any integer $ n\ge2 $, $ \gamma_{I}(P_2\square P_n) = \left\lceil\frac{4n}{3}\right\rceil. $

Proof. Let $ f $ be a $ \gamma_{I}(P_2\square P_n) $-function, $ a_j = f((1, j))+f((2, j)) $ for each $ j\in\{1, 2, \ldots, n\} $ and let $ b_j = a_{j-2}+a_{j-1}+a_{j} $ for each $ j\in\{3, 4, \ldots, n\} $.

Claim 4.3. For each $ j\in\{3, 4, \ldots, n\} $, $ b_j\geq4 $.

Proof of Claim 4.3. Suppose, to the contrary, that there exists some $ j_0\in\{3, 4, \ldots, $ $ n\} $ such that $ b_{j_0}\leq3 $. Note that for each $ j\in\{1, 2, \ldots, n\} $, $ a_j\geq1 $ by Lemma 4.1. Therefore, we have $ b_{j_0} = a_{j_0-2}+a_{j_0-1}+a_{j_0}\ge3 $. This forces $ a_{j_0-2} = a_{j_0-1} = a_{j_0} = 1 $.

Assume first that $ f((2, j_0)) = 1 $. This implies that $ f((1, j_0)) = a_{j_0}-f((2, j_0)) = 0 $. Since $ (1, j_0-1) $ is the unique in-neighbor of $ (1, j_0) $, we have $ f((1, j_0-1)) = 2 $, a contradiction to the fact that $ f((1, j_0-1))\le a_{j_0-1} = 1 $.

Assume second that $ f((2, j_0)) = 0 $. This implies that $ f((1, j_0)) = a_{j_0}-f((2, j_0)) = 1 $. Since $ f $ is a $ \gamma_{I}(P_2\square P_n) $-function, $ f((2, j_0-1))\ge1 $. Moreover, since $ f((2, j_0-1))\le a_{j_0-1} = 1 $, we have $ f((2, j_0-1)) = 1 $ and so $ f((1, j_0-1)) = 0 $. Noting that $ (1, j_0-2) $ is the unique in-neighbor of $ (1, j_0-1) $, we obtain $ f((1, j_0-2)) = 2 $, a contradiction to the fact that $ f((1, j_0-2))\le a_{j_0-2} = 1 $.

So, this claim is true.

Therefore, by Lemma 4.1 and Claim 4.3, we have that if $ n\equiv0\pmod 3 $, then

if $ n\equiv1\pmod 3 $, then

and if $ n\equiv2\pmod 3 $, then

On the other hand, the function $ g $ defined by

is an IDF on $ P_2\square P_n $ and hence

which completes our proof.

We shall give the exact value of the Italian reinforcement number of $ P_2\square P_n $. To our aim, the following lemmas are essential.

Lemma 4.4. Let $ n\ge2 $ be any positive integer and let $ f $ be an IDF on $ P_2\square P_n $. If there exists some $ k\in\{1, 2, \dots, n-1\} $ such that $ f((1, k)) = 1 $ and $ f((2, k)) = 0 $, then the restriction $ f^* $ of $ f $ on $ \{(i, j):1\le i\le2, k+1\le j\le n\} $ is an IDF on $ P_2\square P_{n-k} $.

Proof. Let $ f^* $ be the restriction of $ f $ on $ \{(i, j):1\le i\le2, k+1\le j\le n\} $. Since $ f((1, k)) = 1 $ and $ (1, k) $ is the unique in-neighbor of $ (1, k+1) $, we have $ f((1, k+1))\ge1 $. If $ f((1, k+1)) = 2 $, then clearly $ f^* $ is an IDF on $ P_2\square P_{n-k} $. And if $ f((1, k+1)) = 1 $, then we conclude from $ f((2, k)) = 0 $ and the fact $ (2, k +1) $ has exactly two in-neighbors $ (2, k) $ and $ (1, k+1) $, that $ f((2, k+1))\ge1 $ and hence $ f^* $ is an IDF on $ P_2\square P_{n-k} $.

Lemma 4.5. Let $ n\equiv0\pmod 3 $ be any positive integer and let $ f $ be an IDF on $ P_2\square P_n $. If $ a_n\ge2 $, then $ \omega(f)\ge \frac{4n}{3}+1 $.

Proof. It is easy to check that the restriction $ f^* $ of $ f $ on $ \{(i, j):1\le i\le2, 1\le j\le n-1\} $ is an IDF on $ P_2\square P_{n-1} $ and hence by Theorem 4.2, $ \omega(f^*)\ge \left\lceil\frac{4(n-1)}{3}\right\rceil $. Therefore, we obtain

as desired.

Lemma 4.6. Let $ n\equiv0\pmod 3 $ be any positive integer and let $ f $ be an IDF on $ P_2\square P_n $. If there exists some $ k\in\{1, 2, \dots, n-1\} $ such that $ f((1, k)) = f((2, k)) = 1 $ and $ a_{k+1}\ge2 $, then $ \omega(f)\ge \frac{4n}{3}+1 $.

Proof. Observe that the restriction $ f^*_1 $ of $ f $ on $ \{(i, j):1\le i\le2, 1\le j\le k-1\} $ is an IDF on $ P_2\square P_{k-1} $ and hence by Theorem 4.2, $ \omega(f^*_1)\ge \left\lceil\frac{4(k-1)}{3}\right\rceil $. Let $ f^*_2 $ be the restriction of $ f $ on $ \{(i, j):1\le i\le2, k+1\le j\le n\} $. Since $ (1, k) $ is the unique in-neighbor of $ (1, k+1) $ and $ f((1, k)) = 1 $, we have $ f((1, k+1))\ge1 $. If $ f((1, k+1)) = 1 $, then $ f((2, k+1))\ge1 $ since $ a_{k+1}\ge2 $ and hence $ f^*_2 $ is an IDF on $ P_2\square P_{n-k} $ and if $ f((1, k+1)) = 2 $, then clearly $ f^*_2 $ is also an IDF on $ P_2\square P_{n-k} $. In either case, we conclude from Theorem 4.2 that $ \omega(f^*_2)\ge \left\lceil\frac{4(n-k)}{3}\right\rceil $. Therefore, we obtain

as desired.

Lemma 4.7. Let $ n\equiv0\pmod 3 $ be any positive integer, $ f $ be an IDF on $ P_2\square P_n $ and let $ k\in\{2, 3, \dots, n\} $ such that $ a_{k-1}+a_{k}\ge3 $. If $ n = k $, or $ n > k $ and the restriction $ f^* $ of $ f $ on $ \{(i, j):1\le i\le2, k+1\le j\le n\} $ is an IDF on $ P_2\square P_{n-k} $, then $ \omega(f)\ge \frac{4n}{3}+1 $.

Proof. Observe that the restriction $ f^*_1 $ of $ f $ on $ \{(i, j):1\le i\le2, 1\le j\le k-2\} $ is an IDF on $ P_2\square P_{k-2} $ and hence by Theorem 4.2, $ \omega(f^*_1)\ge \left\lceil\frac{4(k-2)}{3}\right\rceil $. Consequently, if $ n = k $, then

So in the following we may assume that $ n > k $. Since the restriction $ f^* $ of $ f $ on $ \{(i, j):1\le i\le2, k+ 1\le j\le n\} $ is an IDF on $ P_2\square P_{n-k} $ by our assumption, Theorem 4.2 yields $ \omega(f^*)\ge \left\lceil\frac{4(n-k)}{3}\right\rceil $. Therefore, we obtain

as desired.

In the next, we shall determine the Italian reinforcement number of $ P_2\square P_n $.

Theorem 4.8. For any integer $ n\ge2 $,

Proof. If $ n\equiv1\pmod 3 $, then the function $ h_1 $ defined by

is an IDF on $ P_2\square P_n+\{((1, 1), (2, n))\} $ and so $ \omega(h_1) = \left\lceil\frac{4n}{3}\right\rceil-1 < \gamma_I(P_2\square P_n) $ by Theorem 4.2, implying that the set $ \{((1, 1), (2, n))\} $ is an IR-set of $ P_2\square P_n $ and hence $ r_{I}(P_2\square P_n) = 1 $. If $ n\equiv2\pmod 3 $, then the function $ h_2 $ defined by

is an IDF on $ P_2\square P_n+\{((1, 1), (2, n))\} $ and so $ \omega(h_2) = \left\lceil\frac{4n}{3}\right\rceil-1 < \gamma_I(P_2\square P_n) $ by Theorem 4.2, implying that the set $ \{((1, 1), (2, n))\} $ is an IR-set of $ P_2\square P_n $ and hence $ r_{I}(P_2\square P_n) = 1 $. If $ n\equiv0\pmod 3 $, then the function $ h_3 $ defined by

is an IDF on $ P_2\square P_n+\{((1, 1), (1, n)), ((1, 1), (2, n))\} $ and so $ \omega(h_3) = \frac{4n}{3}-1 < \gamma_I(P_2\square P_n) $ by Theorem 4.2, implying that the set $ \{((1, 1), (1, n)), ((1, 1), (2, n))\} $ is an IR-set of $ P_2\square P_n $ and hence $ r_{I}(P_2\square P_n)\le2 $.

It remains to prove that if $ n\equiv0\pmod 3 $, then $ r_{I}(P_2\square P_n)\ge2 $. For the sake of contradiction, we may assume that $ r_{I}(P_2\square P_n) = 1 $. Using Proposition B, there exists a $ \gamma_I(P_2\square P_n) $-function $ f = (V_0, V_1, V_2) $ and a vertex $ v\in V_1 $ such that one of the conditions $ (a) $ and $ (b) $ in Proposition B is true.

Suppose that $ (a) $ is true. Then $ V_2\ne\emptyset $ and there exists some integer $ k\in\{1, 2, \dots, n\} $ such that one of the following holds:

$ \text{(I)} $ $ f((1, k)) = 1 $, $ f((1, k-1)) = f((2, k)) = 0 $, $ f((2, k-1)) = 2 $ and if $ n > k $, then $ f((1, k+1))\ge1 $, where $ v = (1, k) $.

$ \text{(II)} $ $ f((1, k)) = 1 $, $ f((1, k-1)) = 0 $, $ f((2, k))\ge1 $ and if $ n > k $, then $ f((1, k+1))\ge1 $, where $ v = (1, k) $.

$ \text{(III)} $ $ f((2, k)) = 1 $, $ f((2, k-1)) = f((1, k)) = 0 $ and if $ n > k $, then $ f((1, k+1)) = 2 $ and $ f((2, k+1)) = 0 $, where $ v = (2, k) $.

$ \text{(IV)} $ $ f((2, k)) = 1 $, $ f((2, k-1)) = f((1, k)) = 0 $ and if $ n > k $, then $ f((2, k+1))\ge1 $, where $ v = (2, k) $.

First, assume that (I) holds. Notice that $ a_{k-1}+a_{k} = 3 $. Thus if $ n = k $, then by Lemma 4.7, $ \omega(f)\ge \frac{4n}{3}+1 $, a contradiction to Theorem 4.2. And if $ n > k $, then we deduce from Lemma 4.4 that the restriction $ f^* $ of $ f $ on $ \{(i, j):1\le i\le2, k+1\le j\le n\} $ is an IDF on $ P_2\square P_{n-k} $ and hence Lemma 4.7 yields $ \omega(f)\ge \frac{4n}{3}+1 $, a contradiction to Theorem 4.2.

Second, assume that (II) holds. Since $ (1, k-2) $ is the unique in-neighbor of $ (1, k-1) $ and $ f((1, k-1)) = 0 $, we have $ a_{k-2}\ge f((1, k-2)) = 2 $. And by Lemma 4.1, $ a_{k-1}\ge1 $ and so $ a_{k-2}+a_{k-1}\ge3 $. Moreover, since $ f((1, k)) = 1 $ and $ f((2, k))\ge1 $, the restriction $ f^* $ of $ f $ on $ \{(i, j):1\le i\le2, k\le j\le n\} $ is an IDF on $ P_2\square P_{n-k+1} $ and hence Lemma 4.7 yields $ \omega(f)\ge \frac{4n}{3}+1 $, a contradiction to Theorem 4.2.

Finally, assume that (III) or (IV) holds. Since $ (1, k-1) $ is the unique in-neighbor of $ (1, k) $ and $ f((1, k)) = 0 $, we have $ f((1, k-1)) = 2 $ and hence $ a_{k-1}+a_{k} = 3 $. Therefore, if $ n = k $, then by Lemma 4.7, $ \omega(f)\ge \frac{4n}{3}+1 $, a contradiction to Theorem 4.2. Suppose next that $ n > k $. Let $ f^* $ be the restriction of $ f $ on $ \{(i, j):1\le i\le2, k+1\le j\le n\} $. If (III) is true, then clearly $ f^* $ is an IDF on $ P_2\square P_{n-k} $ and hence by Lemma 4.7, $ \omega(f)\ge \frac{4n}{3}+1 $, a contradiction to Theorem 4.2. Assume now that (IV) is true. Since $ (1, k) $ is the unique in-neighbor of $ (1, k+1) $ and $ f((1, k)) = 0 $, we have $ f((1, k+1))\ge1 $. Moreover, since $ f((2, k+1))\ge1 $, $ f^* $ is an IDF on $ P_2\square P_{n-k} $. Thus again by Lemma 4.7, $ \omega(f)\ge \frac{4n}{3}+1 $, a contradiction to Theorem 4.2.

Suppose, next, that $ (b) $ is true. Then there exists some integer $ k\in\{1, 2, \dots, n\} $ such that one of the following holds:

$ \text{(V)} $ $ f((1, k-1)) = f((1, k)) = 1 $, $ f((2, k-1)) = 2 $, $ f((2, k)) = 0 $ and if $ n > k $, then $ f((1, k+1))\ge1 $, where $ v = (1, k) $.

$ \text{(VI)} $ $ f((1, k-1)) = f((1, k)) = 1 $, $ f((2, k))\ge1 $ and if $ n > k $, then $ f((1, k+1))\ge1 $, where $ v = (1, k) $.

$ \text{(VII)} $ $ f((1, k)) = 0 $, $ f((2, k-1)) = f((2, k)) = 1 $ and if $ n > k $, then $ f((1, k+1)) = 2 $ and $ f((2, k+1)) = 0 $, where $ v = (2, k) $.

$ \text{(VIII)} $ $ f((1, k)) = 0 $, $ f((2, k-1)) = f((2, k)) = 1 $ and if $ n > k $, then $ f((2, k+1))\ge1 $, where $ v = (2, k) $.

$ \text{(IX)} $ $ f((1, k)) = f((2, k)) = 1 $, $ f((2, k-1)) = 0 $ and if $ n > k $, then $ f((1, k+1)) = 2 $ and $ f((2, k+1)) = 0 $, where $ v = (2, k) $.

$ \text{(X)} $ $ f((1, k)) = f((2, k)) = 1 $, $ f((2, k-1)) = 0 $ and if $ n > k $, then $ f((2, k+1))\ge1 $, where $ v = (2, k) $.

First, assume that (V) holds. One can check that the function $ g_1 $ defined by $ g_1((2, k-1)) = 1 $ and $ g_1(x) = f(x) $ otherwise, is an IDF on $ P_2\square P_n $ and hence $ \omega(g_1) = \omega(f)-1 < \gamma_I(P_2\square P_n) $, a contradiction.

Second, assume that (VI) holds. If $ n = k $, then $ a_n\ge2 $ and hence by Lemma 4.5, $ \omega(f)\ge \frac{4n}{3}+1 $, a contradiction to Theorem 4.2. Hence we may assume that $ n > k $. Since $ f((1, k+1))\ge1 $, we have that if $ f((2, k)) = 2 $, then the function $ g_2 $ defined by $ g_2((2, k)) = 1 $ and $ g_2(x) = f(x) $ otherwise, is an IDF on $ P_2\square P_n $ and hence $ \omega(g_2) = \omega(f)-1 < \gamma_I(P_2\square P_n) $, a contradiction. As a result, we have $ f((2, k))\le1 $. Moreover, since $ f((2, k))\ge1 $, $ f((2, k)) = 1 $. If $ a_{k+1}\ge2 $, then by Lemma 4.6, $ \omega(f)\ge \frac{4n}{3}+1 $, a contradiction to Theorem 4.2. Thus $ a_{k+1}\le1 $. Moreover, since $ a_{k+1}\ge f((1, k+1))\ge1 $, we have $ a_{k+1} = 1 $. This implies that $ f((1, k+1)) = 1 $ and $ f((2, k+1)) = 0 $. If $ n = k+1 $, then $ a_{n-1}+a_n = 3 $ and so by Lemma 4.7, $ \omega(f)\ge \frac{4n}{3}+1 $, a contradiction to Theorem 4.2. Suppose, next, that $ n > k+1 $. Then Lemma 4.4 yields that the restriction $ f^* $ of $ f $ on $ \{(i, j):1\le i\le2, k+2\le j\le n\} $ is an IDF on $ P_2\square P_{n-k-1} $. Recall that $ a_{k}+a_{k+1} = 3 $. Then by Lemma 4.7, $ \omega(f)\ge \frac{4n}{3}+1 $, a contradiction to Theorem 4.2.

Third, assume that (VII) or (VIII) holds. Since $ (1, k-1) $ is the unique in-neighbor of $ (1, k) $ and $ f((1, k)) = 0 $, this forces $ f((1, k-1)) = 2 $. One can check that the function $ g_3 $ defined by $ g_3((2, k-1)) = 0 $ and $ g_3(x) = f(x) $ otherwise, is an IDF on $ P_2\square P_n $ and hence $ \omega(g_3) = \omega(f)-1 < \gamma_I(P_2\square P_n) $, a contradiction.

Finally, assume that (IX) or (X) holds. If $ n = k $, then Lemma 4.5 yields $ \omega(f)\ge \frac{4n}{3}+1 $ since $ a_n = 2 $, a contradiction to Theorem 4.2. Hence we may assume that $ n > k $. Note that $ f((1, k)) = f((2, k)) = 1 $. If (IX) holds, then $ a_{k+1} = 2 $ and so we conclude from Lemma 4.6 that $ \omega(f)\ge\frac{4n}{3}+1 $, a contradiction to Theorem 4.2. Assume, next, that (X) holds. Since $ (1, k) $ is the unique in-neighbor of $ (1, k+1) $ and $ f((1, k)) = 1 $, we have $ f((1, k+1))\ge1 $ and hence $ a_{k+1} = f((1, k+1))+f((2, k+1))\ge2 $. Moreover, since $ f((1, k)) = f((2, k)) = 1 $, we have $ \omega(f)\ge\frac{4n}{3}+1 $ by Lemma 4.6, a contradiction to Theorem 4.2.

The proof is completed.

Next we determine the exact value of $ \gamma_I(P_3\square P_n) $. We begin with the following lemmas. Analogous to Lemma 4.1, we first obtain the following result.

Lemma 4.9. Let $ n\ge3 $ be an integer and let $ f $ be a $ \gamma_I(P_3\square P_n) $-function. Then $ a_1\ge3 $ and $ a_j\ge1 $ for each $ j\in\{2, 3, \dots, n\} $.

Lemma 4.10. Let $ n\ge3 $ be an integer and let $ f $ be a $ \gamma_I(P_3\square P_n) $-function. If $ a_j = 1 $ for some $ j\in\{2, 3, \dots, n\} $, then $ a_{j-1}\ge3 $.

Proof. Suppose that there exists some $ j\in\{2, 3, \dots, n\} $ such that $ a_j = 1 $. Then $ f((1, j))+f((2, j))+f((3, j)) = 1 $. If $ f((1, j)) = 1 $, then $ f((2, j)) = f((3, j)) = 0 $. This forces $ f((2, j-1))\ge1 $ and $ f((3, j-1)) = 2 $, implying that $ a_{j-1}\ge3 $. If $ f((2, j)) = 1 $, then $ f((1, j)) = f((3, j)) = 0 $. This forces $ f((1, j-1)) = 2 $ and $ f((3, j-1))\ge1 $, implying that $ a_{j-1}\ge3 $. If $ f((3, j)) = 1 $, then $ f((1, j)) = f((2, j)) = 0 $. This forces $ f((1, j-1)) = f((2, j-1)) = 2 $, implying that $ a_{j-1}\ge4 $, which completes our proof.

Theorem 4.11. For any integer $ n\ge3 $, $ \gamma_{I}(P_3\square P_n) = 2n. $

Proof. Let $ f $ be a $ \gamma_{I}(P_3\square P_n) $-function. By Lemmas 4.9 and 4.10, we obtain $ \gamma_{I}(P_3\square P_n) = \omega(f) = \sum_{j = 1}^na_j\ge2n $. Hence it suffices for us to prove that $ \gamma_{I}(P_3\square P_n)\le2n $. If $ n\equiv1(\bmod 3) $, then the function $ g_1 $ defined by

is an IDF on $ P_3\square P_n $ and hence

If $ n\not\equiv1(\bmod 3) $, then the function $ g_2 $ defined by

is an IDF on $ P_2\square P_n $ and hence

which completes our proof.

Kim ^[16] determined the exact value of the cartesian product of two directed cycles $ C_3 $ and $ C_n $ as follows.

Proposition F. For any integer $ n\ge3 $, $ \gamma_{I}(C_3\square C_n) = 2n. $

As a consequence of Theorem 4.11 and Proposition F, we have the following result.

Corollary 4.12. For any integer $ n\ge3 $, $ \gamma_{I}(P_3\square C_n) = \gamma_{I}(C_3\square P_n) = 2n. $

Proof. Since $ P_3\Box P_n $ is a subdigraph of $ P_3\Box C_n $ and $ P_3\Box C_n $ is a subdigraph of $ C_3\Box C_n $, we deduce from Theorem 4.11 and Proposition F that

This implies that $ \gamma_{I}(P_3\square C_n) = 2n. $ Similarly, we have $ \gamma_{I}(C_3\square P_n) = 2n. $

Theorem 4.13. For any integer $ n\ge3 $,

Proof. By Theorem 4.11, Proposition F and Corollary 4.12, we have $ \gamma_{I}(P_3\square P_n) = \gamma_{I}(P_3\square C_n) = \gamma_{I}(C_3\square P_n) = \gamma_{I}(C_3\square C_n) = 2n. $ Moreover, we note that $ P_3\Box P_n $ is a subdigraph of $ P_3\Box C_n $, $ C_3\Box P_n $ and $ C_3\Box C_n $. Thus by Proposition 3.1, it is enough to prove $ r_{I}(P_3\square P_n) = 1 $. One can check that if $ n\equiv1\pmod 3 $ (resp., $ n\not\equiv1\pmod 3 $), then the function $ g_1 $ (resp., $ g_2 $) defined as in Theorem 4.11 is a $ \gamma_{I}(P_3\square P_n) $-function, and $ g_1 $ (resp., $ g_2 $) and the vertex $ (3, 3) $ satisfy the condition $ (a) $ of Proposition B. Thus by Proposition B, $ r_{I}(P_3\square P_n) = 1 $, as desired.

5.   Conclusions

The main objective of this paper is to study the Italian reinforcement number of a digraph $ D $ defined to be the minimum number of arcs which must be added to $ D $ in order to decrease the Italian domination number of $ D $. We first establish some new sharp upper bounds on the Italian reinforcement number and then we determine the exact values of $ r_I(P_2\square P_n) $, $ r_I(P_3\square P_n) $, $ r_I(P_3\square C_n) $, $ r_I(C_3\square P_n) $ and $ r_I(C_3\square C_n) $. Analogous work can be carried out for other digraph parameters such as double Italian domination.

Acknowledgments

This study was supported by the National Natural Science Foundation of China (Nos. 12061007, 11861011) and the Open Project Program of Research Center of Data Science, Technology and Applications, Minjiang University, China.

Conflict of interest

The authors declare no conflict of interest.