The Italian reinforcement number of a digraph is the minimum number of arcs that have to be added to the digraph in order to decrease the Italian domination number. In this paper, we present some new sharp upper bounds on the Italian reinforcement number of a digraph. We also determine the exact values of the Italian reinforcement number of the Cartesian products of directed paths and directed cycles: P2◻Pn, P3◻Pn, P3◻Cn, C3◻Pn and C3◻Cn.
Citation: Zhihong Xie, Guoliang Hao, S. M. Sheikholeslami, Shuting Zeng. On the Italian reinforcement number of a digraph[J]. AIMS Mathematics, 2021, 6(6): 6490-6505. doi: 10.3934/math.2021382
[1] | Ahlam Almulhim . Signed double Italian domination. AIMS Mathematics, 2023, 8(12): 30895-30909. doi: 10.3934/math.20231580 |
[2] | Abel Cabrera-Martínez, Andrea Conchado Peiró, Juan Manuel Rueda-Vázquez . Further results on the total Italian domination number of trees. AIMS Mathematics, 2023, 8(5): 10654-10664. doi: 10.3934/math.2023540 |
[3] | Linyu Li, Jun Yue, Xia Zhang . Double total domination number of Cartesian product of paths. AIMS Mathematics, 2023, 8(4): 9506-9519. doi: 10.3934/math.2023479 |
[4] | Abel Cabrera Martínez, Iztok Peterin, Ismael G. Yero . Roman domination in direct product graphs and rooted product graphs. AIMS Mathematics, 2021, 6(10): 11084-11096. doi: 10.3934/math.2021643 |
[5] | Abel Cabrera-Martínez, Andrea Conchado Peiró . On the $ \{2\} $-domination number of graphs. AIMS Mathematics, 2022, 7(6): 10731-10743. doi: 10.3934/math.2022599 |
[6] | Ana Klobučar Barišić, Antoaneta Klobučar . Double total domination number in certain chemical graphs. AIMS Mathematics, 2022, 7(11): 19629-19640. doi: 10.3934/math.20221076 |
[7] | Rangel Hernández-Ortiz, Luis Pedro Montejano, Juan Alberto Rodríguez-Velázquez . Weak Roman domination in rooted product graphs. AIMS Mathematics, 2021, 6(4): 3641-3653. doi: 10.3934/math.2021217 |
[8] | Fu-Tao Hu, Xing Wei Wang, Ning Li . Characterization of trees with Roman bondage number 1. AIMS Mathematics, 2020, 5(6): 6183-6188. doi: 10.3934/math.2020397 |
[9] | Zepeng Li . A note on the bounds of Roman domination numbers. AIMS Mathematics, 2021, 6(4): 3940-3946. doi: 10.3934/math.2021234 |
[10] | Zongpeng Ding . Skewness and the crossing numbers of graphs. AIMS Mathematics, 2023, 8(10): 23989-23996. doi: 10.3934/math.20231223 |
The Italian reinforcement number of a digraph is the minimum number of arcs that have to be added to the digraph in order to decrease the Italian domination number. In this paper, we present some new sharp upper bounds on the Italian reinforcement number of a digraph. We also determine the exact values of the Italian reinforcement number of the Cartesian products of directed paths and directed cycles: P2◻Pn, P3◻Pn, P3◻Cn, C3◻Pn and C3◻Cn.
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∈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∈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)∪{v} and N−D[v]=N−[v]=N−(v)∪{v}. In general, for a set X⊆V(D), we denote N+D(X)=N+(X)=⋃v∈XN+(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 Δ+(D)=Δ+. Let D1=(V1,A1) and D2=(V2,A2) be two digraphs. The Cartesian product of D1 and D2 is the digraph D1◻D2 with vertex set V1×V2 and for (x1,y1),(x2,y2)∈V(D1◻D2), ((x1,y1),(x2,y2))∈A(D1◻D2) if and only if either (x1,x2)∈A1 and y1=y2, or x1=x2 and (y1,y2)∈A2.
A directed star is a digraph of order n≥2 with vertex set {u1,u2,…,un} and arc set {(u1,ui):2≤i≤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∈X⊆V(D), the private neighborhood pn(v,X) of v is defined by pn(v,X)=N+(v)∖N+(X∖{v}). The complement of a digraph D denoted by ¯D is the digraph with vertex set V(D) defined by (u,v)∈A(¯D) if and only if (u,v)∉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 Cn for the directed cycle of length n, Pn for the directed path of order n. For a real-valued function f:V(D)→R, the weight of f is ω(f)=∑x∈V(D)f(x), and for X⊆V(D), we define f(X)=∑x∈Xf(x), and hence ω(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)→{0,1,2} is an Italian dominating function (IDF) on G if each vertex v∈V(G) assigned 0 under f satisfies ∑x∈N(v)f(x)≥2, where N(v)={x∈V(G):vx∈E(G)}. The minimum value of ∑x∈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)→{0,1,2} is an Italian dominating function (IDF) on a digraph D if each vertex v∈V(D) assigned 0 under f satisfies ∑x∈N−(v)f(x)≥2. The minimum weight of an IDF on D is called the Italian domination number of D and is denoted by γI(D). And we say that a function f is a γI(D)-function if it is an IDF with weight γ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 ¯G be the complement of an undirected graph G. A subset F of E(¯G) is an Italian reinforcement set (IR-set) of G if γI(G+F)≤γ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(¯D) is an Italian reinforcement set (IR-set) of D if γI(D+F)≤γI(D)−1. The Italian reinforcement number of a digraph D, denoted by rI(D), is the minimum size of an IR-set of D. An rI(D)-set is an IR-set F of D with |F|=rI(D). It is clear that if 1≤γI(D)≤2, then addition of arcs does not reduce the Italian domination number. Thus if 1≤γI(D)≤2, then the Italian reinforcement number is defined to be 0. Consequently we always assume that when we discuss rI(D), all digraphs involved satisfy γI(D)≥3.
For an IDF f on D, let Vi={v∈V(D):f(v)=i} for i∈{0,1,2} and hence f can be represented by the ordered triple (V0,V1,V2) (or (Vf0,Vf1,Vf2) 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 rI(P2◻Pn), rI(P3◻Pn), rI(P3◻Cn), rI(C3◻Pn) and rI(C3◻Cn).
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 γI(D)≥3, F be an rI(D)-set and let f be a γI(D+F)-function. Then
(a) For each arc (u,v)∈F, f(u)∈{1,2} and f(v)=0.
(b) γI(D+F)=γI(D)−1.
Proposition B. Let D be a digraph with γI(D)≥3. Then rI(D)=1 if and only if there exist a γI(D)-function f=(V0,V1,V2) and a vertex v∈V1 such that one of the following conditions holds:
(a) f(N−D(v))=0, f(N−D(x)∖{v})≥2 for each x∈N+D(v)∩V0 and V2≠∅.
(b) f(N−D(v))=1 and f(N−D(x)∖{v})≥2 for each x∈N+D(v)∩V0.
Proposition C. For any digraph D of order n with γI(D)≥3,
rI(D)≤n−Δ+−γI(D)+2. |
Proposition D. If D is a digraph of order n≥3 with Δ+(D)≥1 and γI(D)=n, then rI(D)=1.
Hao et al. [8] showed that for any integer n≥3, γI(Pn)=γI(Cn)=n, which, together with Proposition D, would yield the following result directly.
Corollary 2.1. For any integer n≥3, rI(Pn)=rI(Cn)=1.
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 γI(H)=γI(D)≥3. Then rI(D)≤rI(H).
Proof. Let F be an rI(H)-set. Since H+F is a subdigraph of D+(F∖A(D)), we conclude from Proposition A(b) that
γI(D+(F∖A(D)))≤γI(H+F)<γI(H)=γI(D). |
This implies that F∖A(D) is an IR-set of D and so rI(D)≤|F∖A(D)|≤|F|=rI(H), as desired.
Note that Pn is a subdigraph of Cn and γI(Pn)=γI(Cn)=n for n≥3. Moreover, it follows from Corollary 2.1 that rI(Pn)=rI(Cn)=1. This demonstrates the sharpness of Proposition 3.1.
Theorem 3.2. For any digraph D with γI(D)≥3, let f=(V0,V1,V2) be a γI(D)-function. Then
(a) If v∈V1, then rI(D)≤|(N+(v)∖pn(v,V1))∩V0|+2.
(b) If v∈V2, then rI(D)≤|pn(v,V2)∩V0|.
Proof. (a) Let v∈V1. First, assume that V2≠∅. Let w∈V2 and let F=({(w,x):x∈(N+(v)∖pn(v,V1))∩V0}∪{(w,v)})∖A(D). Note that every vertex in pn(v,V1)∩V0 has at least one in-neighbor in V2. Thus the function h1 defined by h1(v)=0 and h1(x)=f(x) for each x∈V(D)∖{v} is an IDF on D+F with ω(h1)=ω(f)−1 and hence F is an IR-set of D, implying that
rI(D)≤|F|≤|(N+(v)∖pn(v,V1))∩V0|+1. |
Second, assume that V2=∅. This forces pn(v,V1)∩V0=∅. Note that there must exist two distinct vertices v1,v2∈V1∖{v} since γI(D)≥3. Let U1=N+(v)∩N+(v1)∩V0, U2=(N+(v)∖N+(v1))∩V0 and let F=({(v1,v),(v2,v)}∪{(v2,x):x∈U1}∪{(v1,x):x∈U2})∖A(D). One can check that the function h1 defined earlier is an IDF on D+F with ω(h1)=ω(f)−1 and hence F is an IR-set of D, implying that
rI(D)≤|F|≤|{(v2,x):x∈U1}∪{(v1,x):x∈U2}|+2=|(N+(v)∩V0)|+2=|(N+(v)∖pn(v,V1))∩V0|+2, |
where the last '=' holds since pn(v,V1)∩V0=∅.
As a result, (a) is true.
(b) Let v∈V2. Then there must exist a vertex w∈V1∪V2 since γI(D)≥3. Let F={(w,x):x∈pn(v,V2)∩V0}∖A(D). It is obvious that the function h2 defined by h2(v)=1 and h2(x)=f(x) for each x∈V(D)∖{v} is an IDF on D+F with ω(h2)=ω(f)−1 and hence F is an IR-set of D, implying that
rI(D)≤|F|≤|pn(v,V2)∩V0|, |
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∪Y, where X={xi:1≤i≤4} and Y={yi:1≤i≤4}, and arc set {(xi,xj),(yi,yj):1≤i≤2,3≤j≤4}. One can check that the function f=({x3,x4,y3,y4},{x1,x2,y1,y2},∅) is a γI(D)-function and hence γI(D)=4.
We next prove that rI(D)≥4. Let F be an rI(D)-set and let g be a γI(D+F)-function. We deduce from Proposition A(b) that ω(g)=γI(D+F)=γ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|≥|X|=4 (resp., |F|≥|Y|=4). So in the following we may assume that g(X)≥1 and g(Y)≥1. Recall that g(X)+g(Y)=ω(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(x2)=0. Since d−D(x2)=0, x2 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|≥4.
Second, assume that exactly two vertices of X are assigned 1 under g. This forces Vg2=∅. Recall that g(Y)=1. If g(y1)=1 (the case g(y2)=1 is similar), then g(y2)=g(y3)=g(y4)=0 and hence y2 is incident from two arcs in F and each of y3 and y4 is incident from one arc in F, implying that |F|≥4. If g(y3)=1 (the case g(y4)=1 is similar), then g(y1)=g(y2)=0 and hence each of y1 and y2 is incident from two arcs in F, implying that |F|≥4.
Therefore, the above arguments mean that rI(D)=|F|≥4. Now let F′={(x1,y2),(x2,y2), (x1,y3),(x1,y4)}. It is not difficult to verify that the function h=({x3,x4,y2,y3,y4},{x1,x2,y1}, ∅) is an IDF on D+F′ with ω(h)=3<γI(D) and hence F′ is an IR-set of D. Thus rI(D)≤|F′|=4. As a result, we obtain rI(D)=4.
Note that f=({x3,x4,y3,y4},{x1,x2,y1,y2},∅) is a γI(D)-function. We have that for 1≤i≤2,
rI(D)=|(N+(xi)∖pn(xi,Vf1))∩Vf0|+2=|(N+(yi)∖pn(yi,Vf1))∩Vf0|+2=4. |
(b) Let t≥s≥3 and p≥1 be arbitrary integers and let D be the digraph with vertex set {ui:1≤i≤s}∪{vi:1≤i≤t}∪{wi:1≤i≤p} and arc set {(u1,ui):2≤i≤s}∪{(v1,vi):2≤i≤t}∪{(u1,wi),(v1,wi):1≤i≤p}.
Let g1 be a γI(D)-function. If there exists some vertex in {u2,u3,…,us} assigned 0 under g1, then g1(u1)=2 and if each vertex in {u2,u3,…,us} is assigned 1 or 2 under g1, then ∑si=2g1(ui)≥s−1. In either case, we have ∑si=1g1(ui)≥2. Similarly, we have ∑ti=1g1(vi)≥2. Therefore, γI(D)≥4. On the other hand, the function f=(V(D)∖{u1,v1},∅,{u1,v1}) is an IDF on D and so γI(D)≤ω(f)=4. Consequently, we have γI(D)=4. This also implies that the function f is a γI(D)-function.
We next prove that rI(D)=s−1. Let F′={(v1,ui):2≤i≤s}. Then the function g2 defined by g2(u1)=1, g2(v1)=2 and g2(x)=0 otherwise, is an IDF on D+F′ with ω(g2)=3<γI(D), and hence F′ is an IR-set of D. Thus rI(D)≤|F′|=s−1. Therefore it is enough to prove that rI(D)≥s−1. Let F be an rI(D)-set and let h be a γI(D+F)-function. We conclude from Proposition A(b) that ω(h)=γI(D+F)=γI(D)−1=3. If ∑ti=1h(vi)∈{0,1}, then at least t−1 vertices in {v1,v2,…,vt} is incident from an arc in F and hence |F|≥t−1≥s−1. If ∑ti=1h(vi)∈{2,3}, then this forces ∑si=1h(ui)∈{0,1} and hence at least s−1 vertices in {u1,u2,…,us} is incident from an arc in F, implying that |F|≥s−1. As a result, we obtain rI(D)=s−1.
Note that the function f=(V(D)∖{u1,v1},∅,{u1,v1}) is a γI(D)-function, |pn(u1,Vf2)∩Vf0|=s−1 and |pn(v1,Vf2)∩Vf0|=t−1. Thus if s=t, then
rI(D)=s−1=|pn(u1,Vf2)∩Vf0|=|pn(v1,Vf2)∩Vf0|. |
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 γI(D)≥3, rI(D)≤Δ++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 γI(D)≥3. Then rI(D)≤⌈n/2⌉.
Proof. If Δ+≤⌈n/2⌉−2, then it follows from Corollary 3.3 that rI(D)≤Δ++2≤⌈n/2⌉. If Δ+≥⌈n/2⌉−1, then by Proposition C, we get
rI(D)≤n−Δ+−γI(D)+2≤n−(⌈n/2⌉−1)−3+2=⌊n/2⌋, |
which completes our proof.
The upper bound of Corollary 3.4 is sharp. For example, let D be the digraph with vertex set {ui,vi:0≤i≤3} and arc set {(ui,vi),(ui,vi+1):0≤i≤3}, where the indices are taken modulo 4. It is not difficult to check that the function f=({vi:0≤i≤3},{ui:0≤i≤3},∅) is the unique γI(D)-function, the set F={(u0,u3),(u1,u3),(u0,v3),(u1,v0)} is an rI(D)-set and g=({u3}∪{vi:0≤i≤3},{ui:0≤i≤2},∅) is a γI(D+F)-function. Therefore rI(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 γI(D)≥3.
Theorem 3.5. For any digraph D with at least one leaf and γI(D)≥3, rI(D)≤max{2,Δ+}.
Proof. Let u be a leaf of D, v be the unique in-neighbor of u and let f be a γI(D)-function. Clearly f(u)≤1. If f(u)=0, then this forces f(v)=2 and it follows from Theorem 3.2(b) that
rI(D)≤|pn(v,Vf2)∩Vf0|≤Δ+≤max{2,Δ+}. |
So in the following we may assume that f(u)=1. It is not different to verify that f(v)≤1. Define the function g by g(u)=0 and g(x)=f(x) for each x∈V(D)∖{u}.
Assume first that f(v)=1. Since γI(D)≥3, there exists some vertex w∈V(D)∖{u,v} such that f(w)≥1 and hence the function g defined earlier is an IDF on D+{(w,u)} with ω(g)=ω(f)−1<γI(D), and so {(w,u)} is an IR-set of D, implying that rI(D)=1<max{2,Δ+}.
Assume next that f(v)=0. Then f(N−(v))≥2. If there exists some vertex w∈N−(v) such that f(w)=2, then the function g defined earlier is an IDF on D+{(w,u)} with ω(g)=ω(f)−1<γI(D), and so {(w,u)} is an IR-set of D, implying that rI(D)=1<max{2,Δ+}. If there exist two different vertices w1,w2∈N−(v) such that f(w1)=f(w2)=1, then the function g defined earlier is an IDF on D+{(w1,u),(w2,u)} with ω(g)=ω(f)−1<γI(D), and so {(w1,u),(w2,u)} is an IR-set of D, implying that rI(D)≤2≤max{2,Δ+}.
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 T with rI(T)=max{2,Δ+(T)}. Let Δ≥2 be an arbitrary integer and let T denote an oriented tree with 1≤Δ+(T)≤Δ. For any vertex u∈V(T), let Su denote a directed star of order Δ with center C(Su). Define T(Δ,T) to be the digraph obtained from T∪(⋃u∈V(T)Su) by adding a new arc (C(Su),u) for each u∈V(T).
Proposition 3.6. For an arbitrary integer Δ≥2, let T be an oriented tree with 1≤Δ+(T)≤Δ and let T=T(Δ,T). Then rI(T)=max{2,Δ+(T)}.
Proof. We now claim that γI(T)=2|V(T)|. It is easy to see that the function h1 defined by h1(C(Su))=2 for each u∈V(T) and h1(x)=0 otherwise, is an IDF on T and hence γI(T)≤ω(h1)=2|V(T)|. Thus it is enough for us to prove that γI(T)≥2|V(T)|. Let h2 be a γI(T)-function. Noting that d−T(C(Su))=0 for each u∈V(T), we have h2(C(Su))≥1 and hence if there exists a leaf x of Su such that h2(x)≥1, then h2(V(Su))≥h2(C(Su))+h2(x)≥2 and if there exists a leaf x of Su such that h2(x)=0, then h2(V(Su))≥h2(C(Su))=2. Consequently, we get
γI(T)=ω(h2)≥∑u∈V(T)h2(V(Su))≥2|V(T)|. |
We next prove that rI(T)=max{2,Δ+(T)}. It follows from Theorem 3.5 that rI(T)≤max{2,Δ+(T)}. Note that max{2,Δ+(T)}=Δ. Thus it is enough for us to prove that rI(T)≥Δ. Let F be an rI(T)-set and f be a γI(T+F)-function.
Claim 3.7. For any vertex u∈V(T) with f(V(Su))≤1, there must exist a vertex in V(Su) incident from an arc in F.
Proof of Claim 3.7. Let u be any vertex of V(T) with f(V(Su))≤1. Note that f(C(Su))≤f(V(Su))≤1. If f(C(Su))=0, then C(Su) is incident from an arc in F since d−T(C(Su))=0, and if f(C(Su))=1, then f(V(Su)∖{C(Su)})=0 and hence each vertex of V(Su)∖{C(Su)} is incident from an arc in F. Thus Claim 3.7 is true.
Claim 3.8. For any vertex u∈V(T) with f(V(Su)∪{u})≤1,
(a) There exist Δ−1 vertices in V(Su)∪{u} incident from an arc in F.
(b) If the number of vertices in V(Su)∪{u} incident from an arc in F is Δ−1, then f(V(Su))=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(Su)∪{u})≤1. It is obvious that f(V(Su))≤1. If f(V(Su))=0, then each vertex of Su is adjacent from an arc in F, and if f(V(Su))=1, then each of exactly Δ−1 vertices of Su 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 γI(T+F)=γI(T)−1=2|V(T)|−1 and hence there exists a vertex u∈V(T) satisfying f(V(Su)∪{u})≤1. Moreover, if there exists a vertex v∈V(T)∖{u} satisfying f(V(Sv)∪{v})≤1, then we conclude from Claim 3.8(a) that |F|≥2(Δ−1)≥Δ. So in the following we may assume that u is the unique vertex satisfying f(V(Su)∪{u})≤1. This implies that f(V(Sw)∪{w})≥2 for each w∈V(T)∖{u}.
If f(V(Su))=0 or u is incident from an arc in F, then we deduce from Claim 3.8 that rI(T)=|F|≥Δ. Suppose, next, that f(V(Su))=1 and u is not incident from an arc in F. This forces f(V(Su)∪{u})=1 and f(u)=0. Furthermore, since ω(f)=γI(T+F)=2|V(T)|−1 and f(V(Sw)∪{w})≥2 for each w∈V(T)∖{u}, one can verify that f(V(Sw)∪{w})=2. Since f(V(Su))=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)≥1. Moreover, it is clear that f(V(Sv)∪{v})=2 since v∈V(T)∖{u} and hence f(V(Sv))=f(V(Sv)∪{v})−f(v)≤1. Thus it follows from Claim 3.7 that there must exist a vertex of V(Sv) incident from an arc in F. Furthermore, since f(V(Su)∪{u})=1, Claim 3.8(a) yields that there exist Δ−1 vertices in V(Su)∪{u} incident from an arc in F. Therefore, we get rI(T)=|F|≥Δ.
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 {u0,u1,…,un−1} as follows. For each i∈{0,1,…,n−1}, the arcs are going from ui to the vertices ui+1,ui+2,…,ui+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
γI(CT(n))={3,if r=1,4,if r≥2. |
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
rI(CT(n))={1, if r=1,r−1, if r≥2. |
Proof. If r=1, that is, if CT(n) is a directed cycle of length 3, then Corollary 2.1 yields rI(CT(n))=1. So in the following we may assume that r≥2. By Propositions C and E, we have
rI(CT(n))≤n−Δ+(CT(n))−γI(CT(n))+2=r−1. |
Hence it suffices to prove that rI(CT(n))≥r−1. Let F be an rI(CT(n))-set and let f=(V0,V1,V2) be a γI(CT(n)+F)-function. Then by Propositions A(b) and E, we have
|V1|+2|V2|=ω(f)=γI(CT(n)+F)=γI(CT(n))−1=3. |
This implies that |V1|=|V2|=1, or |V1|=3 and |V2|=0.
Suppose now that |V1|=|V2|=1. Without loss of generality, assume that u0∈V2 and ui0∈V1 for some i0∈{1,2,…,2r}. Then for each j∈{r+1,r+2,…,2r}∖{i0}, uj∉N+CT(n)(u0) and hence by the definition of γI(CT(n)+F)-function, we have uj is adjacent from one arc in F. Thus rI(CT(n))=|F|≥r−1. Suppose next that |V1|=3 and |V2|=0. Without loss of generality, assume that u0,uk,ul∈V1 for 0<k<l≤2r.
First, assume that l−k<r, where k,l∈{1,2,…,r}. Then N−CT(n)(uj)∩{u0,uk,ul}={u0} for each j∈{1,2,…,k−1}, N−CT(n)(uj)∩{u0,uk,ul}={ul} for each j∈{k+r+1,k+r+2,…,l+r} and N−CT(n)(uj)∩{u0,uk,ul}=∅ for each j∈{l+r+1,l+r+2,…,2r}. This implies that rI(CT(n))=|F|≥r−1.
Second, assume that l−k<r, where k∈{2,3,…,r} and l∈{r+1,r+2,…,2r−1}. Clearly N−CT(n)(uj)∩{u0,uk,ul}={u0} for each j∈{l−r,l−r+1,…,k−1}, N−CT(n)(uj)∩{u0,uk,ul}={uk} for each j∈{r+1,r+2,…,l−1} and N−CT(n)(uj)∩{u0,uk,ul}={ul} for each j∈{k+r+1,k+r+2,…,2r}. This implies that rI(CT(n))=|F|≥r−1.
Third, assume that l−k<r, where k,l∈{r+1,r+2,…,2r}. Clearly N−CT(n)(uj)∩{u0,uk,ul}={u0} for each j∈{l−r,l−r+1,…,r}, N−CT(n)(uj)∩{u0,uk,ul}=∅ for each j∈{r+1,r+2,…,k−1} and N−CT(n)(uj)∩{u0,uk,ul}={uk} for each j∈{k+1,k+2,…,l−1}. This implies that rI(CT(n))=|F|≥r−1.
Finally assume that l−k≥r. Then 1≤k≤r and r+1≤l≤2r. It is clear that N−CT(n)(uj)∩{u0,uk,ul}={uk} for each j∈{r+1,r+2,…,k+r}∖{l}, N−CT(n)(uj)∩{u0,uk,ul}=∅ for each j∈{k+r+1,k+r+2,…,l−1} and N−CT(n)(uj)∩{u0,uk,ul}={ul} for each j∈{l+1,l+2,…,2r}. This implies that rI(CT(n))=|F|≥r−1.
This completes the proof.
In this section, we first determine the exact values of γI(P2◻Pn), γI(P3◻Pn), γI(P3◻Cn) and γI(C3◻Pn), based on which we further determine the exact values of Italian reinforcement number of some classes of cartesian products.
Let m∈{2,3} and n≥m be an integer. We emphasize that V(Pm◻Pn)={(i,j):1≤i≤m,1≤j≤n} and A(Pm◻Pn)={((i,j),(i+1,j)):1≤i≤m−1,1≤j≤n}∪{((i,j),(i,j+1)):1≤i≤m,1≤j≤n−1}. For notational convenience, if f is an IDF on Pm◻Pn, then we denote aj=∑mi=1f((i,j)) for each 1≤j≤n.
Now we consider the exact value of Italian domination number of P2◻Pn. We begin with the following lemma.
Lemma 4.1. Let n≥2 be an integer and let f be a γI(P2◻Pn)-function. Then a1≥2 and aj≥1 for each j∈{2,3,…,n}.
Proof. Since d−((1,1))=0, we have f((1,1))≥1. If f((1,1))=2, then a1≥f((1,1))=2. If f((1,1))=1, then clearly f((2,1))≥1 since (1,1) is the unique in-neighbor of (2,1) and so a1=f((1,1))+f((2,1))≥2. We next show that aj≥1 for each j∈{2,3,…,n}. Suppose, to the contrary, that there exists some j∈{2,3,…,n} such that aj=f((1,j))+f((2,j))=0. Then by the definition of γI(P2◻Pn)-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 P2◻Pn with ω(g)=ω(f)−1<γI(P2◻Pn), a contradiction. As a result, we obtain aj≥1 for each j∈{2,3,…,n}.
Theorem 4.2. For any integer n≥2, γI(P2◻Pn)=⌈4n3⌉.
Proof. Let f be a γI(P2◻Pn)-function, aj=f((1,j))+f((2,j)) for each j∈{1,2,…,n} and let bj=aj−2+aj−1+aj for each j∈{3,4,…,n}.
Claim 4.3. For each j∈{3,4,…,n}, bj≥4.
Proof of Claim 4.3. Suppose, to the contrary, that there exists some j0∈{3,4,…, n} such that bj0≤3. Note that for each j∈{1,2,…,n}, aj≥1 by Lemma 4.1. Therefore, we have bj0=aj0−2+aj0−1+aj0≥3. This forces aj0−2=aj0−1=aj0=1.
Assume first that f((2,j0))=1. This implies that f((1,j0))=aj0−f((2,j0))=0. Since (1,j0−1) is the unique in-neighbor of (1,j0), we have f((1,j0−1))=2, a contradiction to the fact that f((1,j0−1))≤aj0−1=1.
Assume second that f((2,j0))=0. This implies that f((1,j0))=aj0−f((2,j0))=1. Since f is a γI(P2◻Pn)-function, f((2,j0−1))≥1. Moreover, since f((2,j0−1))≤aj0−1=1, we have f((2,j0−1))=1 and so f((1,j0−1))=0. Noting that (1,j0−2) is the unique in-neighbor of (1,j0−1), we obtain f((1,j0−2))=2, a contradiction to the fact that f((1,j0−2))≤aj0−2=1.
So, this claim is true.
Therefore, by Lemma 4.1 and Claim 4.3, we have that if n≡0(mod3), then
γI(P2◻Pn)=n3∑k=1b3k≥4n3=⌈4n3⌉, |
if n≡1(mod3), then
γI(P2◻Pn)=a1+n−13∑k=1b3k+1≥2+4(n−1)3=⌈4n3⌉, |
and if n≡2(mod3), then
γI(P2◻Pn)=a1+a2+n−23∑k=1b3k+2≥3+4(n−2)3=⌈4n3⌉. |
On the other hand, the function g defined by
g((i,j))={1,if i=1 and j≡0(mod3),or i=2 and j≡2(mod3),2,if i=1 and j≡1(mod3),0,otherwise, |
is an IDF on P2◻Pn and hence
γI(P2◻Pn)≤ω(g)=⌊n3⌋+⌈n−13⌉+2×⌈n3⌉=⌈4n3⌉, |
which completes our proof.
We shall give the exact value of the Italian reinforcement number of P2◻Pn. To our aim, the following lemmas are essential.
Lemma 4.4. Let n≥2 be any positive integer and let f be an IDF on P2◻Pn. If there exists some k∈{1,2,…,n−1} such that f((1,k))=1 and f((2,k))=0, then the restriction f∗ of f on {(i,j):1≤i≤2,k+1≤j≤n} is an IDF on P2◻Pn−k.
Proof. Let f∗ be the restriction of f on {(i,j):1≤i≤2,k+1≤j≤n}. Since f((1,k))=1 and (1,k) is the unique in-neighbor of (1,k+1), we have f((1,k+1))≥1. If f((1,k+1))=2, then clearly f∗ is an IDF on P2◻Pn−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))≥1 and hence f∗ is an IDF on P2◻Pn−k.
Lemma 4.5. Let n≡0(mod3) be any positive integer and let f be an IDF on P2◻Pn. If an≥2, then ω(f)≥4n3+1.
Proof. It is easy to check that the restriction f∗ of f on {(i,j):1≤i≤2,1≤j≤n−1} is an IDF on P2◻Pn−1 and hence by Theorem 4.2, ω(f∗)≥⌈4(n−1)3⌉. Therefore, we obtain
ω(f)=ω(f∗)+an≥⌈4(n−1)3⌉+2=4n3+1, |
as desired.
Lemma 4.6. Let n≡0(mod3) be any positive integer and let f be an IDF on P2◻Pn. If there exists some k∈{1,2,…,n−1} such that f((1,k))=f((2,k))=1 and ak+1≥2, then ω(f)≥4n3+1.
Proof. Observe that the restriction f∗1 of f on {(i,j):1≤i≤2,1≤j≤k−1} is an IDF on P2◻Pk−1 and hence by Theorem 4.2, ω(f∗1)≥⌈4(k−1)3⌉. Let f∗2 be the restriction of f on {(i,j):1≤i≤2,k+1≤j≤n}. Since (1,k) is the unique in-neighbor of (1,k+1) and f((1,k))=1, we have f((1,k+1))≥1. If f((1,k+1))=1, then f((2,k+1))≥1 since ak+1≥2 and hence f∗2 is an IDF on P2◻Pn−k and if f((1,k+1))=2, then clearly f∗2 is also an IDF on P2◻Pn−k. In either case, we conclude from Theorem 4.2 that ω(f∗2)≥⌈4(n−k)3⌉. Therefore, we obtain
ω(f)=ω(f∗1)+ω(f∗2)+ak≥⌈4(k−1)3⌉+⌈4(n−k)3⌉+2≥4n3+1, |
as desired.
Lemma 4.7. Let n≡0(mod3) be any positive integer, f be an IDF on P2◻Pn and let k∈{2,3,…,n} such that ak−1+ak≥3. If n=k, or n>k and the restriction f∗ of f on {(i,j):1≤i≤2,k+1≤j≤n} is an IDF on P2◻Pn−k, then ω(f)≥4n3+1.
Proof. Observe that the restriction f∗1 of f on {(i,j):1≤i≤2,1≤j≤k−2} is an IDF on P2◻Pk−2 and hence by Theorem 4.2, ω(f∗1)≥⌈4(k−2)3⌉. Consequently, if n=k, then
ω(f)=ω(f∗1)+an−1+an≥⌈4(k−2)3⌉+3=4n3+1. |
So in the following we may assume that n>k. Since the restriction f∗ of f on {(i,j):1≤i≤2,k+1≤j≤n} is an IDF on P2◻Pn−k by our assumption, Theorem 4.2 yields ω(f∗)≥⌈4(n−k)3⌉. Therefore, we obtain
ω(f)=ω(f∗1)+ω(f∗)+ak−1+ak≥⌈4(k−2)3⌉+⌈4(n−k)3⌉+3=4n3+1, |
as desired.
In the next, we shall determine the Italian reinforcement number of P2◻Pn.
Theorem 4.8. For any integer n≥2,
rI(P2◻Pn)={2, if n≡0(mod3),1, otherwise. |
Proof. If n≡1(mod3), then the function h1 defined by
h1((i,j))={1, if i=1 and j≡0(mod3), or i=1 and j=n, or i=2 and j≡2(mod3),2, if i=1, j≡1(mod3) and j<n,0, otherwise, |
is an IDF on P2◻Pn+{((1,1),(2,n))} and so ω(h1)=⌈4n3⌉−1<γI(P2◻Pn) by Theorem 4.2, implying that the set {((1,1),(2,n))} is an IR-set of P2◻Pn and hence rI(P2◻Pn)=1. If n≡2(mod3), then the function h2 defined by
h2((i,j))={1, if i=1 and j≡0(mod3), or i=2, j≡2(mod3) and j<n,2, if i=1 and j≡1(mod3),0, otherwise, |
is an IDF on P2◻Pn+{((1,1),(2,n))} and so ω(h2)=⌈4n3⌉−1<γI(P2◻Pn) by Theorem 4.2, implying that the set {((1,1),(2,n))} is an IR-set of P2◻Pn and hence rI(P2◻Pn)=1. If n≡0(mod3), then the function h3 defined by
h3((i,j))={1, if i=1, j≡0(mod3) and j<n, or i=2 and j≡2(mod3),2, if i=1 and j≡1(mod3),0, otherwise, |
is an IDF on P2◻Pn+{((1,1),(1,n)),((1,1),(2,n))} and so ω(h3)=4n3−1<γI(P2◻Pn) by Theorem 4.2, implying that the set {((1,1),(1,n)),((1,1),(2,n))} is an IR-set of P2◻Pn and hence rI(P2◻Pn)≤2.
It remains to prove that if n≡0(mod3), then rI(P2◻Pn)≥2. For the sake of contradiction, we may assume that rI(P2◻Pn)=1. Using Proposition B, there exists a γI(P2◻Pn)-function f=(V0,V1,V2) and a vertex v∈V1 such that one of the conditions (a) and (b) in Proposition B is true.
Suppose that (a) is true. Then V2≠∅ and there exists some integer k∈{1,2,…,n} such that one of the following holds:
(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))≥1, where v=(1,k).
(II) f((1,k))=1, f((1,k−1))=0, f((2,k))≥1 and if n>k, then f((1,k+1))≥1, where v=(1,k).
(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).
(IV) f((2,k))=1, f((2,k−1))=f((1,k))=0 and if n>k, then f((2,k+1))≥1, where v=(2,k).
First, assume that (I) holds. Notice that ak−1+ak=3. Thus if n=k, then by Lemma 4.7, ω(f)≥4n3+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≤i≤2,k+1≤j≤n} is an IDF on P2◻Pn−k and hence Lemma 4.7 yields ω(f)≥4n3+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 ak−2≥f((1,k−2))=2. And by Lemma 4.1, ak−1≥1 and so ak−2+ak−1≥3. Moreover, since f((1,k))=1 and f((2,k))≥1, the restriction f∗ of f on {(i,j):1≤i≤2,k≤j≤n} is an IDF on P2◻Pn−k+1 and hence Lemma 4.7 yields ω(f)≥4n3+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 ak−1+ak=3. Therefore, if n=k, then by Lemma 4.7, ω(f)≥4n3+1, a contradiction to Theorem 4.2. Suppose next that n>k. Let f∗ be the restriction of f on {(i,j):1≤i≤2,k+1≤j≤n}. If (III) is true, then clearly f∗ is an IDF on P2◻Pn−k and hence by Lemma 4.7, ω(f)≥4n3+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))≥1. Moreover, since f((2,k+1))≥1, f∗ is an IDF on P2◻Pn−k. Thus again by Lemma 4.7, ω(f)≥4n3+1, a contradiction to Theorem 4.2.
Suppose, next, that (b) is true. Then there exists some integer k∈{1,2,…,n} such that one of the following holds:
(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))≥1, where v=(1,k).
(VI) f((1,k−1))=f((1,k))=1, f((2,k))≥1 and if n>k, then f((1,k+1))≥1, where v=(1,k).
(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).
(VIII) f((1,k))=0, f((2,k−1))=f((2,k))=1 and if n>k, then f((2,k+1))≥1, where v=(2,k).
(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).
(X) f((1,k))=f((2,k))=1, f((2,k−1))=0 and if n>k, then f((2,k+1))≥1, where v=(2,k).
First, assume that (V) holds. One can check that the function g1 defined by g1((2,k−1))=1 and g1(x)=f(x) otherwise, is an IDF on P2◻Pn and hence ω(g1)=ω(f)−1<γI(P2◻Pn), a contradiction.
Second, assume that (VI) holds. If n=k, then an≥2 and hence by Lemma 4.5, ω(f)≥4n3+1, a contradiction to Theorem 4.2. Hence we may assume that n>k. Since f((1,k+1))≥1, we have that if f((2,k))=2, then the function g2 defined by g2((2,k))=1 and g2(x)=f(x) otherwise, is an IDF on P2◻Pn and hence ω(g2)=ω(f)−1<γI(P2◻Pn), a contradiction. As a result, we have f((2,k))≤1. Moreover, since f((2,k))≥1, f((2,k))=1. If ak+1≥2, then by Lemma 4.6, ω(f)≥4n3+1, a contradiction to Theorem 4.2. Thus ak+1≤1. Moreover, since ak+1≥f((1,k+1))≥1, we have ak+1=1. This implies that f((1,k+1))=1 and f((2,k+1))=0. If n=k+1, then an−1+an=3 and so by Lemma 4.7, ω(f)≥4n3+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≤i≤2,k+2≤j≤n} is an IDF on P2◻Pn−k−1. Recall that ak+ak+1=3. Then by Lemma 4.7, ω(f)≥4n3+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 g3 defined by g3((2,k−1))=0 and g3(x)=f(x) otherwise, is an IDF on P2◻Pn and hence ω(g3)=ω(f)−1<γI(P2◻Pn), a contradiction.
Finally, assume that (IX) or (X) holds. If n=k, then Lemma 4.5 yields ω(f)≥4n3+1 since an=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 ak+1=2 and so we conclude from Lemma 4.6 that ω(f)≥4n3+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))≥1 and hence ak+1=f((1,k+1))+f((2,k+1))≥2. Moreover, since f((1,k))=f((2,k))=1, we have ω(f)≥4n3+1 by Lemma 4.6, a contradiction to Theorem 4.2.
The proof is completed.
Next we determine the exact value of γI(P3◻Pn). We begin with the following lemmas. Analogous to Lemma 4.1, we first obtain the following result.
Lemma 4.9. Let n≥3 be an integer and let f be a γI(P3◻Pn)-function. Then a1≥3 and aj≥1 for each j∈{2,3,…,n}.
Lemma 4.10. Let n≥3 be an integer and let f be a γI(P3◻Pn)-function. If aj=1 for some j∈{2,3,…,n}, then aj−1≥3.
Proof. Suppose that there exists some j∈{2,3,…,n} such that aj=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))≥1 and f((3,j−1))=2, implying that aj−1≥3. 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))≥1, implying that aj−1≥3. 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 aj−1≥4, which completes our proof.
Theorem 4.11. For any integer n≥3, γI(P3◻Pn)=2n.
Proof. Let f be a γI(P3◻Pn)-function. By Lemmas 4.9 and 4.10, we obtain γI(P3◻Pn)=ω(f)=∑nj=1aj≥2n. Hence it suffices for us to prove that γI(P3◻Pn)≤2n. If n≡1(mod3), then the function g1 defined by
g1((i,j))={2,if i=1 and j=3k−2 for 1≤k≤(n−1)/3,1,if i∈{1,2} and j=n,or i∈{1,3} and j=3k for 1≤k≤(n−1)/3,or i=2 and j=3k−1 for 1≤k≤(n−1)/3,or i=3 and j=3k−2 for 1≤k≤(n−1)/3,0,otherwise, |
is an IDF on P3◻Pn and hence
γI(P3◻Pn)≤ω(g1)=2×(n−1)/3+2+4×(n−1)/3=2n. |
If n≢1(mod3), then the function g2 defined by
g2((i,j))={2,if i=1 and j=3k−2 for 1≤k≤⌈n/3⌉,1,or i∈{1,3} and j=3k for 1≤k≤⌊n/3⌋,or i=2 and j=3k−1 for 1≤k≤⌈n/3⌉,or i=3 and j=3k−2 for 1≤k≤⌈n/3⌉,0,otherwise, |
is an IDF on P2◻Pn and hence
γI(P3◻Pn)≤ω(g2)=4×⌈n/3⌉+2×⌊n/3⌋=2n, |
which completes our proof.
Kim [16] determined the exact value of the cartesian product of two directed cycles C3 and Cn as follows.
Proposition F. For any integer n≥3, γI(C3◻Cn)=2n.
As a consequence of Theorem 4.11 and Proposition F, we have the following result.
Corollary 4.12. For any integer n≥3, γI(P3◻Cn)=γI(C3◻Pn)=2n.
Proof. Since P3◻Pn is a subdigraph of P3◻Cn and P3◻Cn is a subdigraph of C3◻Cn, we deduce from Theorem 4.11 and Proposition F that
2n=γI(P3◻Pn)≥γI(P3◻Cn)≥γI(C3◻Cn)=2n. |
This implies that γI(P3◻Cn)=2n. Similarly, we have γI(C3◻Pn)=2n.
Theorem 4.13. For any integer n≥3,
rI(P3◻Pn)=rI(P3◻Cn)=rI(C3◻Pn)=rI(C3◻Cn)=1. |
Proof. By Theorem 4.11, Proposition F and Corollary 4.12, we have γI(P3◻Pn)=γI(P3◻Cn)=γI(C3◻Pn)=γI(C3◻Cn)=2n. Moreover, we note that P3◻Pn is a subdigraph of P3◻Cn, C3◻Pn and C3◻Cn. Thus by Proposition 3.1, it is enough to prove rI(P3◻Pn)=1. One can check that if n≡1(mod3) (resp., n≢1(mod3)), then the function g1 (resp., g2) defined as in Theorem 4.11 is a γI(P3◻Pn)-function, and g1 (resp., g2) and the vertex (3,3) satisfy the condition (a) of Proposition B. Thus by Proposition B, rI(P3◻Pn)=1, as desired.
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 rI(P2◻Pn), rI(P3◻Pn), rI(P3◻Cn), rI(C3◻Pn) and rI(C3◻Cn). Analogous work can be carried out for other digraph parameters such as double Italian domination.
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.
The authors declare no conflict of interest.
[1] | F. Azvin, N. Jafari Rad, L. Volkmann, Bounds on the outer-independent double Italian domination number, Commun. Comb. Optim., 6 (2021), 123–136. |
[2] |
M. Chellali, T. W. Haynes, S. T. Hedetniemi, A. A. McRae, Roman {2}-domination, Discrete Appl. Math., 204 (2016), 22–28. doi: 10.1016/j.dam.2015.11.013
![]() |
[3] |
M. Chellai, N. Jafari Rad, S. M. Sheikholeslami, L. Volkmann, Varieties of Roman domination II, AKCE Int. J. Graphs Combin., 17 (2020), 966–984. doi: 10.1016/j.akcej.2019.12.001
![]() |
[4] | M. Chellali, N. Jafari Rad, S. M. Sheikholeslami, L. Volkmann, A survey on Roman domination parameters in directed graphs, J. Combin. Math. Combin. Comput., to appear. |
[5] | M. Chellali, N. Jafari Rad, S. M. Sheikholeslami, L. Volkmann, Varieties of Roman domination, In: T. W. Haynes, S. T. Hedetniemi, M. A. Henning, Structures of Domination in Graphs, Springer International Publishing, 2021. |
[6] |
H. Gao, T. T. Xu, Y. S. Yang, Bagging approach for Italian domination in Cn◻Pm, IEEE Access, 7 (2019), 105224–105234. doi: 10.1109/ACCESS.2019.2931053
![]() |
[7] | S. C. Garcá, A. C. Martínez, F. A. H. Mira, I. G. Yero, Total Roman {2}-domination in graphs, Quaestiones Math., 2019. Available from: https://doi.org/10.2989/16073606.2019.1695230. |
[8] | G. L. Hao, X. Chen, Y. Zhang, A note on Roman {2}-domination in digraphs, Ars Combin., 145 (2019), 185–193. |
[9] |
G. L. Hao, S. M. Sheikholeslami, S. L. Wei, Italian reinforcement number in graphs, IEEE Access, 7 (2019), 184448–184456. doi: 10.1109/ACCESS.2019.2960390
![]() |
[10] | T. W. Haynes, S. T. Hedetniemi, P. J. Slater, Fundamentals of Domination in Graphs, New York: Marcel Dekker Inc, 1998. |
[11] | T. W. Haynes, S. T. Hedetniemi, P. J. Slater, Domination in Graphs, Advanced Topics, New York: Marcel Dekker Inc, 1998. |
[12] |
T. W. Haynes, M. A. Henning, Perfect Italian domination in trees, Discrete Appl. Math., 260 (2019), 164–177. doi: 10.1016/j.dam.2019.01.038
![]() |
[13] |
T. W. Haynes, M. A. Henning, L. Volkmann, Graphs with large Italian domination number, Bull. Malays. Math. Sci. Soc., 43 (2020), 1–15. doi: 10.1007/s40840-018-0660-7
![]() |
[14] |
M. A. Henning, W. F. Klostermeyer, Italian domination in trees, Discrete Appl. Math., 217 (2017), 557–564. doi: 10.1016/j.dam.2016.09.035
![]() |
[15] | K. Kim, The Italian bondage and reinforcement numbers of digraphs, 2020. Available from: https://arXiv.org/abs/2008.05140. |
[16] | K. Kim, The Italian domination numbers of some product of directed cycles, Mathematics, 8 (2020), 1472. Available from: https://doi.org/10.3390/math8091472. |
[17] |
A. Rahmouni, M. Chellali, Independent Roman {2}-domiantion in graphs, Discrete Appl. Math., 236 (2018), 408–414. doi: 10.1016/j.dam.2017.10.028
![]() |
[18] | L. Volkmann, Italian domination in digraphs, J. Combin. Math. Combin. Comput., to appear. |
[19] | L. Volkmann, The Italian domatic number of a digraph, Commun. Comb. Optim., 4 (2019), 61–70. |
1. | Ahlam Almulhim, Bana Al Subaiei, Saiful Rahman Mondal, Survey on Roman {2}-Domination, 2024, 12, 2227-7390, 2771, 10.3390/math12172771 |