# Total Roman2-Reinforcement of Graphs

Authors: M. Kheibari; H. Abdollahzadeh Ahangar; R. Khoeilar; S. M. Sheikholeslami
Journal: Journal of Mathematics
 (2021)

---

## Abstract

A total Roman2-dominating function (TR2DF) on a graph Γ=V,E is a function l:V⟶0,1,2, satisfying the conditions that (i) for every vertex y∈V with ly=0, either y is adjacent to a vertex labeled 2 under l, or y is adjacent to at least two vertices labeled 1; (ii) the subgraph induced by the set of vertices with positive weight has no isolated vertex. The weight of a TR2DF l is the value ∑y∈Vly. The total Roman 2-domination number (TR2D-number) of a graph Γ is the minimum weight of a TR2DF on Γ. The total Roman 2-reinforcement number (TR2R-number) of a graph is the minimum number of edges that have to be added to the graph in order to decrease the TR2D-number. In this manuscript, we study the properties of TR2R-number and we present some sharp upper bounds. In particular, we determine the exact value of TR2R-numbers of some classes of graphs.


---

## Body

## 1. Introduction

A total dominating set (TDS)D in an isolated-free graph Γ is a set of vertices of Γ such that each vertex in VΓ is adjacent to a vertex of D. The total domination number γtΓ of Γ is the minimum cardinality of a TDS. Sridharan et al. [1] introduced the total reinforcement number rtΓ of a graph Γ as the minimum number of edges that have to be added to the graph in order to decrease the total domination number.. Since the domination number of any isolated-free graph Γ is greater than or equal to 2, by convention, Sridharan, Elias, and Subramanian defined rtΓ=0 if γtΓ=2.A functionl:VΓ⟶0,1,2 is a R2DF of Γ if each vertex y∈VΓ labeled 0 under l satisfies ∑z∈Nylz≥2, where Ny=z∈VΓ:yz∈EΓ. The minimum value ∑z∈VΓlz of a R2DF l on Γ is called the R2D-number of Γ. The R2DF was introduced in [2] and has been studied by several authors [3–13]. For more details on R2D-number, we refer the reader to the recent book chapter [14] and survey paper [15].As a new variant of Roman2-domination, total Roman 2-domination was investigated in [16, 17], where it was called total Roman 2-domination. A TR2DF on a graph Γ is defined as a function l:VΓ⟶0,1,2, satisfying the conditions: (i) for every vertex y∈VΓ with ly=0, lNy≥2, that is, either there is a vertex w∈Ny with lw=2, or at least two vertices z1,z2∈Ny with lz1=lz2=1; (ii) the subgraph induced by the set of vertices with positive weight under l has no isolated vertex. The weight of a TR2DF l is the value ωl=lVΓ. The TR2D-number of a graph Γ, denoted by γtR2Γ, is the minimum weight of a TR2DF on Γ. A TR2DF on Γ with weight γtR2Γ is called a γtR2Γ-function. For a sake of simplicity, at TR2DF l on Γ will be represented by the ordered partition V0,V1,V2 (or V0l,V1l,V2l to refer l) of VΓ induced by l, where Vi=y∈VΓ:ly=i, for i∈0,1,2. Since labeling 2 to the vertices of any minimum total domination set of a graph Γ introduces a TR2DF of Γ, we have(1)γtR2Γ≤2γtΓ.In this paper, we extend the idea of Roman {2}-reinforcement number to TR2R-number as follows: for a graphΓ, a subset M of EΓ¯ is a total Roman {2}-reinforcement set (TR2RS) of Γ if γtR2Γ+M<γtR2Γ. The TR2R-number of a graph Γ, denoted by rtR2Γ, is the minimum cardinality of a TR2RS of Γ. A TR2Rtotal Roman {2}-reinforcement set (TR2RS M of Γ is called a rtR2Γ-set if M=rtR2Γ. Observe that if γtR2Γ=2, then addition of edges does not reduce the TR2D-number. We put rtR2Γ=0 if γtR2Γ=2. Hence, we always suppose that when we discuss rtR2Γ, all graphs involved satisfy γtR2Γ≥3. If Γ is a graph such that γtR2≥3, then there is always a nonempty set M⊆EΓ¯ such that γtR2Γ+M<γtR2Γ, i.e., rtR2Γ≥1. For instance, if we take M=EΓ¯, then we have that 2=γtR2Γ+M<3≤γtR2Γ.Our purpose in this manuscript is to initiate the study of TR2R-number in graphs. We derive some sharp upper bounds onrtR2Γ and we also determine exact values of TR2R-number of paths and complete multipartite graphs.We close this section with some useful results.Observation 1.
For any graphΓ with γtR2Γ≥3 and γtR2Γ-function l=V0,V1,V2, pny,l≠∅, for every y∈V2.Proposition 1.
For any graphΓ with γtR2Γ≥3, let M be a rtR2Γ-set and let l be a γtR2Γ+M-function. Then, the following hold:(i)
For any edgev1v2∈M, lv1,lv2≠0.(ii)
γtR2Γ−2≤γtR2Γ+M≤γtR2Γ−1.Proof.
(i)
Suppose, to the contrary, that there exists an edgev1v2∈M such that lvi=0 for each i∈1,2. Then, l is a TR2DF on Γ+M−v1v2 and so M−v1v2 is a TR2DS of Γ, implying that rtR2Γ≤M−v1v2=M−1, a contradiction. Hence, (i) holds.(ii)
SinceM is a rtR2Γ-set, γtR2Γ+M≤γtR2Γ−1. Now, we prove the lower bound. If γtR2∈3,4, then we are done. Now, we assume that γtR2≥5 and suppose, to the contrary, that γtR2Γ+M≤γtR2Γ−3. Let v1v2∈M. By (i), we can suppose that lv2≥1. If lv1=0, then the function s, defined by sv1=1 and sz=lz for the other vertices, is a TR2DF on Γ+M−v1v2 with ωs=ωl+1≤γtR2Γ−1, and so M−v1v2 is a TR2-set of Γ, implying that rtR2Γ≤M−v1v2=M−1, a contradiction. Assume that lv1≥1. Let ui be a neighbor of vi in Γ for i=1,2. Then, the function s, defined by sui=max1,lui for i=1,2 and sx=lx for the other vertices, is a TR2DF on Γ+M−v1v2 with ωs=ωl+2≤γtR2Γ−1, and so M−v1v2 is a TR2-set of Γ, implying that rtR2Γ≤M−v1v2=M−1, a contradiction. So (ii) also holds.Proposition 2.
(see [16, 17]). Let Γ be a nontrivial connected graph of order p. Then, γtR2Γ=p if and only if Γ∈K2,P3 or any vertex of Γ is either a leaf or a weak stem.Theorem 1.
(see [18]). If Γ is a connected graph of order p≥3 and ΔΓ≤p−2, then γtΓ≤p−ΔΓ.


## 2. Bounds

The aim of this section is to obtain basic properties of the TR2R-number in graphs. LetΓ be a graph and l=V0,V1,V2 be a TR2DF. For each y∈V1∪V2, the l-private neighborhood of y, denoted by pny,l, consists of all vertices z∈Ny∩V0 such that ∑w∈Nzlw=2.Theorem 2.
LetΓ be a graph with γtR2Γ≥3 and let l=V0,V1,V2 be a γtR2Γ-function. Then, the following assertions hold.(i)
For anyy∈V2, rtR2Γ≤pny,l. This bound is sharp for double star DSr,ss≥r≥2.(ii)
IfV1+V2≥3, then for each y∈V1,(2)rtR2Γ≤pny,l+Il2+1,when Il is the set of all isolate vertices of induced subgraph ΓV1∪V2−y.Proof.
(i)
Letv∈V2. By definition, there exists u∈Nv∩V1∪V2. Let M=ux|x∈pnv,l. Notice that M≠∅ by Observation 1. Then, the function s defined by sv=1 and sy=ly, for the other vertices, is a TR2DF of Γ+M and so rtR2Γ≤M=pnv,l.(ii)
Letv∈V1. By definition, there exists w∈Nv∩V1∪V2. Let pnv,l=w1,w2,…,wt if pnv,l≠∅ and Il=z1,z2,…,zs when Il≠∅. Since V1+V2≥3, for any vertex x∈pnv,l∪Il, there is a vertex x′∈V1∪V2 such that xx′∉EΓ. Let M=xx′|x∈pnv,l∪z2i−1z2i|1≤i≤t−1/2∪ztzt′ when t is odd and M=xx′|x∈pnv,l∪z2i−1z2i|1≤i≤t/2 if t is even. If v joins at least two vertices in V1∪V2, then the function s defined by sv=0, sy=ly, for the other vertices, is a TR2DF of Γ+M. If v joins only one V1∪V2 and v′∈V1∪V2−Nv, then the function s, defined before, is a TR2DF of Γ+M∪vv′. Hence,(3)rtR2Γ≤M+1≤pnv,l+Il2+1.Proposition 3.
LetΓ be a graph. Then, rtR2Γ≤ΔΓ+1.Proof.
IfγtR2Γ=2, then rtR2Γ=0<Δ+1. Hence, assume that γtR2Γ≥3 and let l=V0,V1,V2 be a γtR2Γ-function. If V2≠∅ and v∈V2, then by Theorem 2(i), we have rtR2Γ≤pnv,l≤Δ−1. Assume that V2=∅. Then, we have γtR2Γ=V1≥3. In this case, the result holds by Theorem 2(ii).Proposition 4.
LetΓ be a graph of order p with γtR2Γ≥4. Then,(4)rtR2Γ≤p−Δ−1.Proof.
Letv be a vertex of degree Δ. Since γtR2Γ≥4, we have VΓ∖NΓv=p−ΔΓ−1≥1. Let u∈Nv and VΓ∖NΓv=u1,…,ut. Then, the function s defined by sv=2,su=1 and sx=0, for the other vertices, is a TR2DF on Γ+vui|1≤i≤p−ΔΓ−1 with ωs=3. Thus, M is a TR2-set of Γ and so rtR2Γ≤M=p−Δ−1, establishing the desired upper bound.Next result is an immediate consequence of Propositions3 and 4.Corollary 1.
For any graphΓ of order p with γtR2Γ≥4,(5)rtR2Γ≤p2.This bound is sharp forP5.Proof.
IfΔ≤⌊p/2⌋−1, then Proposition 3 yields rtR2Γ≤Δ+1≤⌊p/2⌋. If Δ≥⌊p/2⌋, then by Proposition 4, we obtain rtR2Γ≤p−Δ−1≤p−⌊p/2⌋−1=⌊p/2⌋.LetΓk be the graph obtained from two copies of K2∨Kk¯k≥4 by joining exactly two vertices of degree 2 to obtain a connected graph (for k=4, see Figure 1). Clearly, ΔΓk=k+1 and γtR2Γk=4, and it is not hard to see that rtR2Γk=ΔΓk+1. This shows that the bounds established in Theorem 2(ii), Propositions 3 and 4, and Corollary 1 are sharp.Figure 1
The graphΓ4.Theorem 3.
LetΓ be a graph of order p≥3. If rtR2Γ≠0, then(6)rtR2Γ≤p−ΔΓ−γtR22+1.Proof.
It is enough to show thatγtR2Γ≤2p−2ΔΓ−2rtR2Γ+2. Since ΔΓ≤p−1−rtR2Γ (see Proposition 4), we add rtR2Γ−1 edges incident with a vertex of maximum degree and call such that a set of edges F. Clearly, γtR2Γ=γtR2Γ+F. Clearly, ΔΓ+F≤n−2 and by Theorem 1, γtΓ+F≤p−ΔΓ+F. Using inequality (1), we obtain(7)γtR2Γ=γtR2Γ+F≤2γtΓ+F≤2p−2ΔΓ+F≤2p−2ΔΓ−2rtR2Γ+2.Next, we consider graphsΓ with γtR2Γ∈2γtΓ,2γtΓ−1.Proposition 5.
LetΓ be a graph with γtR2Γ∈2γtΓ,2γtΓ−1. Then,(8)rrR2Γ≤rtΓ.Proof.
LetF be a rtΓ-set. By inequality (1), we have γtR2Γ+F≤2γtΓ+F≤2γtΓ−2<γtR2Γ and this implies that rtR2Γ≤F=rtΓ.


## 3. GraphsΓ with Small rtR2

In this section, we provide sufficient conditions for the graph to have smallrtR2. We first give a characterization of graphs Γ with rtR2Γ=1.Lemma 1.
LetΓ be a connected graph of order p≥3 with γtR2Γ=p. Then, rtR2Γ=1.Proof.
LetγtR2Γ=p. If Γ is the P3=xyz, then Γ+xz is a complete graph and so γtR2Γ+xz=2<γtR2Γ. Assume that Γ is the corona graph Γ=H∘K1 of some connected graphs H of order greater than or equal to two. Let y1 and y2 be two leaves in Γ. Then, Γ+y1y2 is not a corona graph and it follows from Proposition 2 that γtR2Γ+y1y2≤p−1<γtR2Γ. Thus, rtR2Γ=1.Theorem 4.
LetΓ be a connected graph of order p≥3. Then, rtR2Γ=1 if and only if γtR2Γ=p or there exists a function l=V0,V1,V2 of weight less that γtR2Γ for which one of the following conditions holds.(i)
For eachz∈V0, ∑u∈Nzlu≥2, V1∪V2≥2, and the induced subgraph ΓV1∪V2 has at most two isolated vertices.(ii)
ΓV1∪V2 has no isolated vertices and ∑u∈Nzlu≥2 for each vertex z∈V0 except one, say w, such that ∑u∈Nwlu≤1 if V2≠∅ or ∑u∈Nwlu=1 if V2=∅.Proof.
According to Lemma1, we can suppose that γtR2Γ≤p−1. Let there exist a function l=V0,V1,V2 of weight less that γtR2Γ, satisfying (i) or (ii). Since ωl≤p−2, we have V1∪V2≠∅. First, let l satisfy (ii) and let z∈V0 be a vertex for which ∑u∈Nzlu≤1. Suppose u∈V1∪V2 is a vertex for which uz∉EΓ and lu is as large as possible. Clearly, l is a TR2DF of Γ+uz and this implies that rtR2Γ=1. Next, assume that l satisfies (i). If ΓV1∪V2 has two isolated vertices u,v, then l is a TR2DF of Γ+uv and if ΓV1∪V2 has exactly one isolate vertex, say u, then l is a TR2DF of Γ+uv, where v∈V1∪V2−u. This implies that rtR2Γ=1.
Conversely, assume thatrtR2Γ=1, and let M=e=zy be a rtR2Γ-set. If γtR2Γ=p, then we are done. Hence, we assume that γtR2Γ≤p−1. Let l be a γtR2Γ+e-function. If z,y∈V1∪V2, then l satisfies item (i) and if z∈V0 or y∈V0, then l satisfies item (ii).Next, we consider connected graphs with minimum degree 1.Proposition 6.
LetΓ be a connected graph of order p≥3. If Γ has a stem v, then rtR2Γ≤degv. This bound is sharp for P5.Proof.
Ifp=3, then Γ=P3 and the result follows from Proposition 2 and Lemma 1. Assume that p≥4. Let u be a leaf-neighbor of v and l be a γtR2Γ-function such that lu is as small as possible. If lu=0, then lv=2, and by Theorem 2, we have rtR2Γ≤pnv,l≤degv−1. Assume that lu≥1. Then, by the choice of l, we must have lu=lv=1. Since n≥4 and u is a leaf, we have V1∪V2≥3. Let w∈V1∪V2∖u,v. Then, the function s, defined by su=0 and sy=ly for the other vertices, is a TR2DF of Γ+uw,vw of weight less than γtR2Γ. Hence, rtR2Γ≤2≤degv.Proposition 7.
IfΓ is a connected graph containing a path v1v2v3v4v5 in which dvi=2 for i∈2,3,4, then rtR2Γ≤3.Proof.
Ifv1 or v5 is a leaf, then the desired result follows by Proposition 6. Hence, we suppose degv1≥2 and degv5≥2. Let l=V0,V1,V2 be a γtR2Γ-function. If lv3=2, then to totally dominate v3, we can suppose without loss of generality that lv2≥1 and the function s:VΓ+v2v4⟶2, defined by sv3=1 and sy=ly for the other vertices, is a TR2DF of Γ+v2v4 of weight less than γtR2Γ. Assume that lv3≤1. Likewise, we can suppose that lv2,lv4≤1. We consider two cases.
Case 1.lv3=1.
To totally dominatev3, we can suppose that lv2≥1. If lv4=1, then the function s:VΓ+v2v4⟶2, defined by sv3=0 and sy=ly for the other vertices, is a TR2DF of Γ+v2v4 of weight less than γtR2Γ. Suppose that lv4=0. Then, to Roman 2-dominate v4, we must have lv5≥1 and the function s:VΓ+v2v4,v3v5,v2v5⟶2, defined by sv3=0 and sy=ly for the other vertices, is a TR2DF of Γ+v2v4,v2v5,v3v5 of weight less than γtR2Γ.
Case 2.lv3=0.
Sincelv2,lv4≤1, to Roman 2-dominate v3, we must have lv2=lv4=1 and to totally dominate v2,v4, we must have lv1≥1 and lv5≥1, respectively. Define s:VΓ+v2v4,v1v4,v3v5⟶2 by sv2=0 and sy=ly for the other vertices. Clearly, s is a TR2DF of Γ+v2v4,v1v4,v3v5 of weight less that of γtR2Γ. All in all, we have rtR2Γ≤3.


## 4. Exact Values

In this section, we determine the TR2R-number of paths and complete multipartite graphs. The TR2D-number of paths is determined in [17].Proposition 8.
(see [17]). For any positive integer p≥2,(i)
γtR2Pp=2⌈p/3⌉+1ifp≡0mod32⌈p/3⌉otherwise.(ii)
γtR2Cp=⌈2p/3⌉.Theorem 5.
For any integerp≥3,(9)rtR2Pp=1,ifp≡0,1mod3,2,otherwise.Proof.
LetPp=v1,v2,…,vp. If p≡0,1mod3, then by Proposition 8, we have γtR2Pn+v1vp<γtR2Pp and hence rtR2Pp=1.
Suppose next thatp≡2mod3. Clearly, the function l defined by lv1=lvi=0 for i≡0mod3, and lx=1 otherwise, is a TR2DF on Pp+v1vp,v2vp with ωl=2⌈p/3⌉−1=γtR2Pp−1 implying that rtR2Pp≤2. Now, we show that rtR2Pp≥2. In order to this, we show that there is no function l′=V0,V1,V2 of weight less than γtR2Γ, satisfying one of the conditions (i) and (ii) of Theorem 4.
Suppose, to the contrary, that there exists a functionl′=V0,V1,V2 of weight less than γtR2Γ, satisfying one of the conditions (i) and (ii) of Theorem 4. Choose such a function l′ such that V2 is as few as possible. Let p=3r+2 for some positive integers r. First, let l′ satisfy (ii). We note that V2=∅; otherwise, if vi∈V2, then by total, we can suppose that l′vi+1≥1 and the function s defined by svi−1=svi=1, and sy=l′y otherwise, is a function on Pp of weight less than γtR2Γ, satisfying (ii), a contradiction with the choice of l′. Then, we must have V1≤2r+1 and so V0≥r+1. Assume without loss of generality that vi1,vi2,…,vir⊆V0 such that i1<⋯<ir and ∑u∈Nvijl′u≥2 for each 1≤j≤r. Then, we must have l′vij−1=l′vij+1=1. Since ΓV1 has no isolated vertex, we have l′vij−2=l′vij+2=1 for each 1≤j≤r. It follows that V1≥2r+2 which is a contradiction.
Now, letl′ satisfy (i). Using the above argument, we can see that each vertex in V2 is isolated in ΓV1∪V2. Thus, V2≤2. First, let V2=2. Since V1+2V2=V1+4≤2r+1, we have V1≤2r−3 and this implies that V0≥r+3. Clearly, four vertices in V0 are dominated by vertices with weight 2. Assume without loss of generality that vi1,vi2,…,vir−1⊆V0 in which i1<⋯<ir−1 and that vj has no neighbor in V2. As mentioned above, we can see that V1≥2r which leads to the contradiction V1+2V2≥2r+4.
Next, assume thatV2=1. Let l′vi=2. We claim that i≤p−2. If i=p, then the function s defined by svp=svp−1=1 and sy=l′y is a TR2DF of Pp of weight less than γtR2Γ which is a contradiction. If i=p−1, then we must have l′vp=l′vp−2=0 and l′vp−3≥1 (note that V2=1) and the function s, defined before, is a TR2DF of Pp of weight less than γtR2Γ, a contradiction again. Thus, i≤p−2. Similarly, we can see that i≥3. Since V2=1, we must have l′vi−2=l′vi+2=1. Then, the function s, defined by svi−1=svi+1=1,svi=0 and sy=l′y otherwise, is a function on Pp of weight less than γtR2Γ, a contradiction.
Finally, letV2=0. We distinguish two situations.(1)
ΓV1 has exactly one isolated vertex, say vi. If i=1 (the case i=p is similar), then l′v2=0 and the function s, defined by sv1=0,sv2=1 and sy=l′y otherwise, is a function of weight less than γtR2Γ which satisfies (ii) and the result follows as above. Thus, 2≤i≤p−1. Then, l′vi−1=l′vi+1=0. To Roman 2-dominate vi−1 and vi+1, we must have l′vi−2=l′vi+2=1. On the other hand, since vi is the only isolated vertex of ΓV1, we have l′vi−3=l′vi+3=1. Let P1 be the path obtained from Pp by deleting the vertices vi−2,vi−1,vi,vi+1,vi+2 and adding the edge vi−3vi+3. Clearly, the restriction of l′ on P1 is a TR2DF of P1, and by Proposition 8, we have ωl′≥3+2r−1=2r+2 which is a contradiction.(2)
ΓV1 has exactly two isolated vertices. Let vi,vj be the isolated vertices of ΓV1 such that j>i. Note that if i=1, then l′v2=0, and to Roman 2-dominate v2, we must have l′v3=1. Now, if l′v4=0, then we must have l′v5=l′v6=1 and then the function s, defined by sv2=1 and sy=l′y otherwise, is a TR2DF of Pp−v1 implying that ωs=ωl′=2r+2 which is a contradiction. Assume that l′v4=1. Then, the function l′, defined by l′v3=0,l′v2=1 and sy=l′x otherwise, is a function of weight ωl′, satisfying the condition (i) of Theorem 4. Thus, we can suppose that i≥2. Similarly, we can suppose that j≤p−1. Then, we must have l′vi−1=l′vi+1=l′vj−1=l′vj+1=0. To Roman 2-dominate vi−1,vj−1,vi+1 and vj+1, we must have l′vi−2=l′vi+2=l′vj−2=l′vj+2=1, and to totally dominate vi−2 and vj+2, we have l′vi−3=l′vj+3=1. If i=j−2, then the restriction of l′ on P2, obtained from Pp by deleting the vertices vi−2,vi−1,vi,vi+1,vj,vj+1,vj+2 and adding the edge vi−3vj+3, is a TR2DF of P2, and by Proposition 8, we have ωl′≥4+2r−2=2r+2 which is a contradiction. If i=j−5, then l′vi+2=l′vi+3=1, and the restriction of l′ on P3, obtained from Pp by deleting the vertices vi−2,…,vj+2 and adding the edge vi−3vj+3, is a TR2DF of P3, and by Proposition 8, we have ωl′≥6+2r−4=2r+2, a contradiction again. Let i<j−5. Then, we must have l′vi+2=l′vi+3=l′vj−2=l′vj−3=1 and the restriction of l′ on P4, obtained from Pp by deleting the vertices vi−2,vi−1,vi,vi+1,vi+2,vj−2,vj−1,vj,vj+1,vj+2 and adding the edges vi−3vi+3,vj−3vj+3, is a TR2DF of P4, and by Proposition 8, we have ωl′≥6+2r−4=2r+2 which is a contradiction.
Thus, there is no functionl=V0,V1,V2 of weight less than γtR2Γ, satisfying one of the conditions (i) and (ii) of Theorem 4. So, rtR2Pp=2.The proof of the following result is straightforward and then omitted.Proposition 9.
For any positive integersp1≤p2≤⋯≤pt with t≥2,(10)γtR2Kp1,p2,…,pt=2,ifp1=p2=1,3,ifp1=1andp2≥2,3,ifp1≥2andt≥3,3,ifp1=2andt=2,4,ifp1≥3andt=2.Next, we determine the TR2R-number of complete multipartite graphs.Theorem 6.
For any positive integers1≤p1≤p2≤⋯≤pt with t≥2,(11)rtR2Kp1,p2,…,pt=0,ifp1=p2=1,1,ifpi=2for somei,p2−1,ifp1=1,p2≥2,p1−1,ifp1≥3andt=2,2p1−3,ifp1≥3andt≥3.Proof.
LetΓ=Kp1,p2,…,pt. If p1=p2=1, then γtR2Γ=2, and by definition, we have rtR2Γ=0. If pi=2 for some i and x,y is a partite set of size 2, then the function s, defined by sx=sy=1 and sz=0 otherwise, is a TR2DF of Γ+xy of weight 2 and this implies that rtR2Γ=1. Hence, we assume that p2≥3. First, let p1=1. By Proposition 9, we have γtR2Γ=3. Let M be a rtR2Γ-set. Then, we have γtR2Γ+M=2. Let l be a γtR2Γ+M-function and lx=ly=1. If x,y belong to a partite set x,y,x1,…,xpi−2, then to dominate x1,…,xpi−2, we must have xxi,yxi∈M, and to totally dominate x,y, we must have xy∈M. This implies that M≥2pi−2+1=2pi−3. If x,y belong to different partite sets, say x∈x,x1,…,xpi−1 and y∈y,y1,…,ypj−1 where j≥i, then clearly we must have xxs,yyℓ∈F for each s and each ℓ, yielding M≥pi+pj−2≥pj−1. In either case, M≥p2−1. Let x be the vertex of the partite set of size 1 and y be a vertex of a partite set y,y1,…,yp2−1. Clearly, the function s, defined by sx=sy=1 and sz=0 otherwise, is a TR2DF of Γ+yys|1≤s≤p2−1 of weight 2 and this implies that rtR2Γ=p2−1.
Now, letp1≥3. Assume that t≥3 and let M be a rtR2Γ-set. Then, γtR2Γ+M=2. Let l be a γtR2Γ+M-function and let lx=ly=1. As mentioned above, we can see that M≥2p1−3. If X=x1,…,xp1 is a partite set, then the function s, defined by sx1=sx2=1 and sz=0 otherwise, is a TR2DF of Γ+x1x2,x1xs,x2xs|2≤s≤p1 of weight 2 and so rtR2Γ=2p1−3.
Assume now thatt=2 and let X1=x11,…,xp11 and X2=x12,…,xp22 be the partite sets of Γ. Let M be a rtR2Γ-set and let l=V0,V1,V2 be a γtR2Γ+M-function. Then, we have γtR2Γ+M=3. We consider the following situations:(i)
V2=V1=1.LetV2=x and V1=y. If x,y belong to a partite set Xi, then we can suppose that x=x1i,y=x2i. Then, to dominate the vertices in Xi−x,y and to totally dominate the vertices x,y, we must have x1ixsi∈M for 2≤s≤pi and so M≥pi−1≥p1−1. If x,y belong to different partite sets, then we can suppose that x=x11 and y=x12. Then, to dominate the vertices X1−x, we must have xxs1∈M for 2≤s≤p1 and so M≥p1−1. On the other side, the function s, defined by sx11=2,sx21=1 and sz=0 otherwise, is a TR2DF of Γ+x11xs1|2≤s≤p1 of weight 3 and so rtR2Γ=p1−1.(ii)
V2=0 and V1=3.IfV1⊆Xi and V1=x1i,x2i,x3i, then to dominate the vertices xsis≥4, M must contain two edges between xsi and V1 for each 4≤s≤p1 and to totally dominate the vertices of V1, M must contain two edges between x1i,x2i,x3i. It follows that M≥2ni−3+2=p1−1.IfV1 intersects both X1,X2, then V1∩Xi=2 for some i, and as mentioned above, we can see that M≥pi−1≥p1−1. On the other side, the function s, defined by sx11=2,sx21=1 and sz=0 otherwise, is a TR2DF of Γ+x11xs1|2≤s≤p1 of weight 3 and so rtR2Γ=p1−1.Proposition 10.
For any integerp≥3, rtR2Cp=1 if p≡1,2mod3 and rtR2Cp≤3 if p≡0mod3.Proof.
LetCp=y1y2,…,ypy1. If p≡1,2mod3, then the function l, defined by ly1=ly3i=0 for 1≤i≤⌊p/3⌋, is a TR2DF on Cp+y2yp with ωl=⌈2p/3⌉−1=γtR2Cp−1. Thus, the set y2yp is a TR2-set of Cp and so rtR2Cp=1.
Suppose next thatp≡0mod3. Using Proposition 3, we have rtR2Cp≤Δ+1=3.



---

*Source: 5515250-2021-04-12.xml*