# Reinforcement Number of a Graph with respect to Half-Domination

Authors: G. Muhiuddin; N. Sridharan; D. Al-Kadi; S. Amutha; M. E. Elnair
Journal: Journal of Mathematics
 (2021)

---

## Abstract

In this paper, we introduce the concept of reinforcement number with respect to half-domination and initiate a study on this parameter. Furthermore, we obtain various upper bounds for this parameter. AMS subject classification: 05C38, 05C40, 05C69.


---

## Body

## 1. Introduction

Throughout our discussion, we consider only simple finite graphs. For graph theoretic terminologies, we refer the readers to [1]. If G=V,E is a graph to each vertex v of G, N1v denotes the set of all vertices of G which are adjacent to v. For any subset S⊆V, N1S=∪N1v:v∈S. For a vertex v of G, N1v=N1v∪v and N2v=u∈V:du,v=2. A vertex v∈V is said to dominate itself and its adjacent vertices. In other words, a vertex v dominates a vertex u if u∈N1v. A subset D of VG is said to be a dominating set of G if V=∪v∈DN1v. The minimum cardinality of a dominating set D of G is denoted by γG and is called the domination number of G. The total domination number of a graph G, denoted by γtG, is the minimum cardinality of a total dominating set of G and, for their properties, we refer the reader to [2–6]. In [7], Kulli introduced the concept of the cobondage number cbG of a graph, which is the minimum number of edges to be added to reduce the domination number. The same concept has been independently introduced and studied earlier by others under the name “reinforcement number” (refer to chapter 17 of Haynes et al.’s work [8]). Total reinforcement number of a graph has been studied in [9–12]. Recently, Muhiuddin et al. have studied various related concepts on graphs (see, e.g., [13–17]).In [18, 19], a new domination parameter γλG, where 0<λ<1, was introduced and a study on γ1/2G had been initiated. In this paper, we introduce the concept of reinforcement number with respect to half-domination and initiate a study on this parameter.


## 2. Definition and Examples

IfG is a graph for every vertix u of G, we define a map fu:VG⟶0,1/2,1 as follows:(1)fuv=1,if du,v≤1,12,if dv,u=2,0,otherwise,for all v∈VG. The map fu is called the half-domination factor of u.A subsetD of VG is said to be a 1/2-dominating set for G if, for each v∈VG, ∑u∈Dfuv≥1. The minimum cardinality of a 1/2-dominating set is called the 1/2-domination number of G and is denoted by γ1/2G. A 1/2-dominating set of G with the minimum cardinality γ1/2G is said to be a γ1/2-set of G. The parameter γ1/2G was introduced in [18] and bounds for γ1/2G are obtained in [18].Theorem 1 (see [18]).
IfG is a graph on n vertices and ΔG=Δ, then(2)n1+1/2Δ+1/2Δ2≤γ1/2G≤n−Δ.Theorem 2 (see [18]).
IfG is a connected graph with ΔG≤n−3, then γ1/2G≤n−Δ−1. Moreover, trees T with ΔT≤n−3, and γ1/2G=n−Δ−1 are characterized in [18].Definition 1 (reinforcement number with respect to half-domination).
LetG be a graph with γ1/2G≥2. The reinforcement number with respect to half-domination is denoted by ℛ1/2G and is given by ℛ1/2G=minA:A⊆EG¯andγ1/2G+A<γ1/2G. For graphs G, with γ1/2G=1, ℛ1/2G is not defined.Remark 1.
Ifγ1/2G=2, then ℛ1/2G=n−Δ−1 (let u be a vertex of G with degu=Δ. If A=uv:v∉N1u, then u is a γ1/2-dominating set for G+A).
ℛ1/2G for some standard graphs: here, we discuss path Pn on n vertices. As γ1/2Pn=2, if n=4,5,6,7, it follows that ℛ1/2P4=1, ℛ1/2P5=2, ℛ1/2P6=3, and ℛ1/2P7=4.Theorem 3.
Ifn≥8, then ℛ1/2Pn=1ifn≡0,1mod42ifn≡2,3mod4.Proof.
γ1/2Pn=⌊n/4⌋+1 for all n. Let Pn be v1,v2,…,vn. If n=4k or 4k+1k≥2, then D=v2+4i:0≤i≤k−1∪v4k is a γ1/2-set of Pn. If e=v2vn, then e∈EPn¯ and D−v4k is a half-dominating set for Pn+e. Thus, ℛ1/2Pn=1 if n=4k or 4k+1, k≥2.
Ifn=4k+2 or 4k+3k≥2, then D=v2+4i:0≤i≤k is a γ1/2-set of Pn. Let e1=v2v7 and e2=v5v4k+2. Then, D−v6 is a half-dominating set for Pn+A, where A=e1,e2. Thus, ℛ1/2Pn≤2. We claim that ℛ1/2Pn≥2. If ℛ1/2Pn=1, then there is a subset S of Pn and an edge e∈EPn¯ such that S=k and S is a half-dominating set for Pn+e. With respect the path Pn, either Nu1∩S≠ϕ or Nun∩S≠ϕ (otherwise, S cannot be a half-dominating set of Pn+e). In Pn (by ignoring the contribution by the edge e), fSV≤4k−1/2. So, n−fSV≥5/2. But the contribution by the edge e will be at most 2. Thus, S cannot be a half-dominating set for Pn+e, which is a contradiction. Thus, ℛ1/2Pn≥2, if n=4k+2 or 4k+3k≥2.
One can easily prove the following theorem.Theorem 4.
IfCn is a cycle on n-vertices n≥3, then(3)ℛ1/2Cn=n−3,if3≤n≤8,1,ifn=9or4k+1or4k+2,k≥3,2,ifn=10or4kor4k+3,k≥3.Remark 2.
We compareℛ1/2G, the reinforcement number of G with respect to 1/2-domination, and ℛtG, the reinforcement number with respect to the total-domination for some graphs, to show that there is no correlation between ℛ1/2G and ℛtG.(a)
IfG=P8, the path on eight vertices, γ1/2P8=3 and ℛ1/2P8=1, while γtP8=4 and ℛtP8=3(b)
IfG=P9, the path on nine vertices, γ1/2P9=3 and ℛ1/2P9=1, while γtP9=5 and ℛtP9=1(c)
IfG=C8, the cycle on eight vertices, γ1/2C8=2 and ℛ1/2C8=5, while γtC8=4 and ℛtC8=2Theorem 5.
IfT is a tree with γ1/2T≥3, then ℛ1/2T≤3.Proof.
Asγ1/2T≥3, diamT≥3. Let u1u2,…,ul be a diagonal path in T (so du1,ul=diamT). Let D be a γ1/2-set of T. We can assume that u2∈D. If u3∈D, let e=u2x for some x≠u2,u3∈D. Then D−u2 is a half-dominating set for T+e. Assume that u3∉D. If Nu3∩D≥3, select x,y∈D′=D−u2. Let A=u2x,u2y. Then D′=D−u2 is a half-dominating set of T+A. If Nu3∩D≤2, find x,y∈D′=D−u2, such that y∉Nu3. Let e1=u2x, e2=u2y, and e3=u3y. Then D′ is a half-dominating set for G+A, where A=e1,e2,e3. Thus, ℛ1/2T≤3, for all trees T with γ1/2T≥3.Remark 3.
An example for a treeT, with ℛ1/2T=3, is given in Figure 1.Figure 1
Example for a treeT, with γ1/2t=4 and ℛ1/2T=3.


## 3. Bounds forℛ1/2G

In this section, we obtain certain bounds forℛ1/2G. If γ1/2G=2, then ℛ1/2G=n−ΔG−1. First, we have the following theorem.Theorem 6.
Ifγ1/2G≥2, then ℛ1/2G≤n−ΔG−γ1/2G+1≤n−Δ−1.Proof.
LetG be a graph with γ1/2G=k≥2. Let u be a vertex of degree Δ. As k≥2, V−Nu contains at least k−1 vertices. Select a subset S of VG such that S=k−1 and S∩Nu=u. Let A=uv:v∉S∪Nu and uv∈EG¯. Then S is a dominating set of G+A. Thus, γ1/2G+A≤k−1 and ℛ1/2G≤A≤n−Δ−k−1=n−Δ−k+1≤n−Δ−1, as k≥2.Corollary 1.
Ifγ1/2G≠1, ℛ1/2G=n−Δ−1 if γ1/2G=2.As a corollary, we get a better upper bound forγ1/2G which is given by inequality (1).Corollary 2.
For all graphsG with 1≤δ≤Δ≤n−2, γ1/2G≤n−Δ−ℛ1/2G+1.Proof.
LetG be a connected graph with γ1/2G=k≥3. Let D=u1,u2,…,uk be a γ1/2-set of G. Let V0=D, V1=N1D−D, and V2=V−N1D. Note that if v∈V2, then v∈N2ui∩N2uj for some i,j, 1≤i<j≤k. Then, V=V0∪V1∪V2 is a partition of VG. As D is a γ1/2-set of G, to each ui, D−ui is not a half-dominating set of G and hence the set Pui,D, called private neighbors of ui, consisting of all v∈VG which are not half-dominated by the set D−ui, is not empty. Note that Pui,D=P1ui,D∪P2ui,D, where P1ui,D=v∈V:Nv∩D=ui and N2v∩D≤1 and P2ui,D=v∈V:v∉ND,ui∈N2vandN2v∩D=2. As Pui,D≠ϕ, either P1ui,D≠ϕ or P2ui,D≠ϕ. We write Pui, P1ui, and P2ui for Pui,D, P1ui,D, and P2ui,D, respectively. Now, we observe the following.Observation 1.
D=γ1/2G≤γG≤V1=N1D−D.Proof.
AsD is a γ1/2-set of G, for each ui, either P1ui≠ϕ or P2ui≠ϕ, so Nui−D≠ϕ for each i, 1≤i≤k. Hence, V1 is a dominating set of G. Thus, D=γ1/2G≤γG≤V1.Observation 2.
Ifγ1/2G≥3 and D=N1D for at least one γ1/2-set D of G, then ℛ1/2G≤2.Proof.
IfD=N1D, then N1D=V1 is also a γ1/2-set of G and the maximum degree of the induced subgraph V1≤1 (if, for some x∈V1, degx≥2 in V1≤1, then V1−x is also a half-dominating set of G, which is a contradiction as V1=D=γ1/2G). If xy is an edge in V1, select a vertex z≠x,y∈V1 (note that V1=D≥3). Then V1−x is a half-dominating set for G+e, where e=xy. Thus, in this case, ℛ1/2G=1. If V1 is an independent set in G, select x,y,z∈V1. Let A=xy,xz⊆EG¯. Then, V1−x is a half-dominating set for G+A. Thus, ℛ1/2G≤A=2.Observation 3.
IfV2=ϕ for some γ1/2-set D of G, then ℛ1/2G≤2.Proof.
IfV2=ϕ, P2u1=ϕ and hence D−u is a half-dominating set of G+u1u2,u1u3.Observation 4.
IfG is a connected graph with γ1/2G=k≥3, then ℛ1/2G≤2n/k−2≤2n/3−2.Proof.
IfP2ui=ϕ for any i, 1≤i≤k (with respect to some γ1/2-set D of G), then, by our Observation 1, ℛ1/2G≤2 and so ℛ1/2G≤2n/k−2 (as G is connected, 2k≤n). If D=V0=V1, then also ℛ1/2G≤2 and hence the result is true. So assume that D<V1 and P2ui≠ϕ for all i, 1≤i≤k. If x∈P2ui,D, for some i, then x∈P2uj,D for exactly one j≠i. Thus, each x∈P2uj,D is counted twice in ∑i=1kP2ui,D. As V1≥k+1, V2=V−N1D≤n−2k+1. So, ∑P2ui≤2V2≤2n−4k−2 and hence we can find one uj such that P2uj≤2n−4k−2/k. To each vertex w∈P2uj, select a vertex x∈N1uj such that xw is an edge in G, and select a vertex ui such that w∉N2ui (since N2w∩D=2, there is a vertex ui∈D such that w∉N2ui), and let ew=xv∈EG¯. Let A=ew:w∈P2uj∪ujui,ujui2, where i1≠i2 and j∉i1,i2. Then, γ1/2G+A≤k−1 and hence ℛ1/2G≤A+2=P2uj+2≤2n−4k−2/k+2=2n−1/k−2.Observation 5.
IfN1ui=1, for some ui in a γ1/2-set D, then ℛ1/2≤2.Observation 6.
For a connected graphG, with radius of G≥3 and γ1/2G≥3, ℛ1/2G≤n−Δ−δ−γ1/2+1 (radius of G≥3⟹ to each vertex x∈v, there is a vertex y such that dx,y≥3).Proof.
Letk=γ1/2G. Let v1 be a vertex of G with degv1=Δ. Let v2 be a vertex such that dv1,v2≥3. Then, N1v1∩N1v2=ϕ. Let B=V−N1v1∪N1v2. Then, B contains at least k−3 vertices. Select k−2 vertices v3,v4,…,vk−1 in B. Let A=v1x:x∈B−v3,…,vk−1. Note that A⊂EG¯. Now, S=vi:1≤i≤k−1 is a half-dominating set for G+A. So ℛ1/2G≤n−Δ−δ−k+1, where k=γ1/2G.Remark 4.
The upper bound given in Observation6 is attained by the graph in Figure 2. For this graph, n=9, γ1/2G=3, Δ=4, δ=2, and ℛ1/2G=1.Figure 2
A group G for whichℛ1/2G=n−Δ−δ−γ1/2G+1.Remark 5.
For a connected graphG with radius ≥3 and γ1/2G≥3, Observation 6 yields a better bound for γ1/2G than the bound given by inequality (1). γ1/2G≤n−Δ−δ−ℛ1/2G+1. In the following theorem, we obtain an upper bound for ℛ1/2G in terms of ΔG.Theorem 7.
For any graphG, with γ1/2G≥3, ℛ1/2G≤2Δ.Proof.
LetD be a γ1/2-set of G. Select three vertices u,v,w in D. Let A=xv,xw:x∈Nu∩EG¯. Then, A≤2degu≤2ΔG and D−u is a half-dominating set of G+A; thus, ℛ1/2G≤2Δ.Remark 6.
There are graphsG, for which γ1/2G≥3 and ℛ1/2G=2Δ.Example 1.
(Example for a graphG with γ1/2G≥3 and ℛ1/2G=2Δ). Consider the graph G given in Figure 3. First, we note that for this graph n=21, Δ=3, δ=2, and n/1+Δ/2+Δ2/2=γ1/2G=3. (γ1/2G attains its lower bound given in (1). The set D=a,b,c is the unique γ1/2-set of G (for any vertex s∈VG, fsV≤n/1+Δ/2+Δ2/2=7 and fsV=7 if s∈D and fsV<7 for all s∉D. If D′ is any three-element subset of V, other than D, then fD′V<21). VG=V1∪V2∪V3, where V1=a,b,c, V2=xi,yi,zi:1≤i≤3, and V3=uij,vij,wij:1≤i<j≤3. Assume that B is a two-element subset of V and A⊂EG¯ such that B is a half-domination set of G+A. In order to show that ℛ1/2G=6, it is enough to prove that A≥6. Claim: A≥6.
In our further discussion, we consider the following notations.
Ife∈A, we write Tes, where s∈VG, and the number Tes=∑t∈BftsinG+e−∑t∈BftsinG. We say that the edge e∈A contributes the value λ to a vertex s of G if λ=Tes. Similarly, we say that e contributes the value λ to VG if λ=TeV=∑s∈VTes. If A′⊂A, we define TA′s=∑t∈BftsinG+A−∑t∈BftsinG and TA′V=∑s∈VTA′s. We note that Tes≤1 for all e∈A and s∈VG. We can also assume that every edge e in A has one end in B. Now, we establish our claim A≥6 by considering various possibilities for B (for each possibility, we consider one subcase; other subcases can be proved similarly):Case (i):B⊂V1. Assume that B=a,b. Then fBs=1/2 if s∈u13,v13,w13,u23,v23,w23. If, for an edge e∈A, Tes0≥1/2 for one of the elements s0 in u13,v13,w13, then Tss=0 for s≠s0∈u13,v13,w13 and b is one of the ends of e. Similarly, if Tes0≥1/2 for one s0∈u23,v23,w23, then Tes=0 for s≠s0∈u23,v23,w23 and a is one of the ends of e. Thus, A≥6.Case (ii):B⊂V2. Assume that B=x1,z2. Then fBs=1/2 if s∈y1,y2,x3,z3 and fBs=0 if s∈c,y3,u23,w13,v12,v13,v23. Let A′⊂A be such that TA′y1,TA′y2≥1/2; TA′s≥1 for s∈v12,v13,v23,z3; and TeY≥1/2 for every e∈A′, where Y=y1,y2,y3,v12,v13,v23. Then A′≥3; TA′c≥1/2 only if A′≥4. If A′=4, A−A′ contains at least two edges e1 and e2 so that Te1u23≥1/2 and Te2w13≥1/2. So, in this case, A≥6. If A′=3, A−A′ contains a set A″ of at least three edges such that TA″s≥1, where s∈c,u23,v23. Thus, in this case, also A≥6.Case (iii):B⊂V3. Assume that B=u12,w13. Then fBs=1/2 if s∈u13,u23,w12,w23,b,c and fBs=0 if s∈y1,y2,y3,v12,v13,v23,x3,z2. If A′⊂A such that TA′s≥1 for s∈y1,y2,y3,v12,v13,v23, then A′≥4 (A′ contains at least two edges with one end at u12 and at least two edges with one end at w13). A−A′ contains an edge e1 with one end at w13 and Te1u13≥1/2 and contains another edge e2 with one end at u12 and Tew23≥1/2. Thus, A≥6.Case (iv):B∩V1≠ϕ and B∩V2≠ϕ. Assume that B=a,x2. Then, fBs=1/2 if s∈u13,v13,w13,v12,w12,x2,y2,z2 and fBs=0 if s∈c,y3,z3,w23,v23. The set A contains a subset A′, with A′=3, TA′s≥1/2 for s∈u12,v13,w13, and each edge in A′ has one end at x2. Note that TA′c≤1/2, either TA′w23=0 or TA′w12=0, and either TA′v12=0 or TA′v23=0. So, there is a set A″ contained in A−A′ with A″≥3 such that TB∪A′∪A″s≥1 for s∈c,w23,v12,w12,w23. Thus, 6≤A′+A″≤A.Case (v):B∩V1≠ϕ and B∩V3≠ϕ. Assume that B=a,w23. Then, fBs=1/2 if s∈u12,u13,v12,v13,b,c and fBs=0 if s∈x2,x3,y2,y3,u23,v23. There are edges e1 and e2 in A with one end at a and Te1c≥1/2. Note that Te1u23+Te2u23≤1/2 and Te1v23+Te2v23≤1/2. There are edges e3 and e4 in A, with one end at w23 and Te3u13≥1/2; Te4v13≥1/2. Now either Te3u23=0 or Te3u12=0, and either Te4v23=0 or Te4v12=0. As A1=e1,e2,e3,e4⊂A and TAs≥1/2 for s∈c,b,u13,u12,v12,v13 and TAs≥1 for s∈u23,v23, we have A≥6.Case (vi):B∩V2≠ϕ and B∩V3≠ϕ. Let B=x1,v23. Then fBs=1/2 for s∈c,b,u13,u12,v12,v13 and fBs=0 if s∈z2,z3,w12,w23,w13,u23. The set A should contain at least three edges to attribute positive values to z1,z2,z3,w12,w23; it should contain at least two edges with one end at v23 to contribute positive values to y1 and x3 and one edge with one end at x1 to contribute a positive value to v13. Thus, A≥6. The upper bound 2Δ for ℛ1/2G can be reduced further if Δ<γ1/2G.Figure 3
A graphG with γ1/2G=3 and ℛ1/2G=2Δ=6.Theorem 8.
Ifγ1/2G≥3 and ΔG<γ1/2G, then(4)ℛ1/2G≤Δ,ifΔG<γ1/2G−1,Δ+1,ifΔG=γ1/2G−1.Proof.
Letγ1/2G=k≥3. Let D=u1,u2,…,uk be a γ1/2-set of G. Let N1u1−D=v1,v2,…,vl. Let 1≤j≤l. If P2u1∩N1vj=ϕ, select one ij2≤ij≤k such that uijvj∈EG¯. If P2u1∩N1vj≠ϕ, then either N1vj∩D=u1 or N1vj∩D=2. If N1vj∩D=u1, then, for each vertex w∈P2u1∩N1vj, i:i≠1andw∈N2ui=1. So, we can select one ij2≤ij≤k such that P2u1∩N1vj∩N2uij=ϕ (this is possible since P2u1∩N1vj≤δ−1<γ1/2G−1). Thus, to each vj,1≤j≤l, we have selected one uij∈D−u1. If ΔG<γ1/2G−1, we can select uil such that uil≠ui1. Let A=vjuij:1≤j≤l. If ΔG<γ1/2G−1, D−u1 is a half-dominating set of G+A. If ΔG<γ1/2G−1, then D−u1 is a half-dominating set of G+A+e1, where e1=u1uj for some uj∉Nu1 (as D−u1 is not a half-dominating set of G, Nu1≠D−u1). Thus, ℛ1/2G≤l≤Δ if ΔG<k−1 and ℛ1/2G≤l+1≤Δ+1 if ΔG=k−1. In the following theorem, we obtain a lower bound for ℛ1/2G of some classes of graphs.Theorem 9.
IfG is a connected graph with γ1/2G=k≥3 and the order n=k1+Δ/2+Δ2/2, then ℛ1/2G≥Δ.Proof.
IfS=u1,u2,…,uk−1 is a set of vertices of G, then fsV≤k−11+Δ/2+Δ2/2. If S is a half-dominating set of G+A, where A⊆EG¯, then A should contribute at least 1+Δ/2+Δ2/2 to the total ∑fsV in G+A. But Te is an edge e in A which can contribute at most 1+Δ/2. So, A≥1+Δ/2+Δ2/2/1+Δ/2=Δ−1+2/1+Δ. Hence, A≥Δ whenever γ1/2G+A≤k−1. Thus, ℛ1/2G≥Δ.Corollary 3.
If, for a graphG with γ1/2G=k≥3, Δ<k−1 and n=k1+Δ/2+Δ2/2, then ℛ1/2G=Δ.Example 2.
IfΔ=2, γ1/2G=k≥4, and n=k1+Δ/2+Δ2/2 for a connected graph G, then G=C4k for k≥4. We know that ℛ1/2C4k=2 for all k≥3.Remark 7.
For allk≥3 and Δ<k−1, we can construct graphs G with γ1/2G=k, ΔG=Δ, and n=k1+Δ/2+Δ2/2. Now, we list some properties of graphs G with γ1/2G≥3 and ℛ1/2G=2Δ. Let D=u1,u2,…,uk be any γ1/2-set of G (where k=γ1/2G). Then,(1)
k=γ1/2≤Δ(2)
degui=Δ for all i, 1≤i≤k(3)
Nui∩Nuj=ϕ for all 1≤i<j≤k(4)
P2ui∩N1v∩N2uj≠0 for all i≠j∈1,2,…,k and for all v∈N1ui. So P2ui∩N1v≥k−1∀1≤i≤k and v∈N1uiProblem 1.
Characterize the graphsG with γ1/2G≥3 and ℛ1/2G=2ΔG.


## 4. Nordhaus-Gaddum-Type Results

IfG is a graph with 1≤δ≤Δ≤n−2, both ℛ1/2G and ℛ1/2G¯ are defined. In this section, we obtain certain bounds for the sum ℛ1/2G+ℛ1/2G¯. We use the following notations:Ifv∈VG, then N1¯v=u∈V/v≠uandvu∈EG¯ and N2¯v=u∈V/du,v=2inG¯. Also, δ¯ and Δ¯ denote the minimum degree and maximum degree of G¯, respectively. Note that δ¯=n−ΔG−1 and Δ¯=n−δG−1.Theorem 10.
If1≤δG≤ΔG≤n−2, then ℛ1/2G+ℛ1/2G¯≤n−Δ−δ−1≤n−1.Proof.
By Theorem6, ℛ1/2G≤n−ΔG−1 and ℛ1/2G¯≤n−Δ¯−1.(5)ℛ1/2G+ℛ1/2G¯≤n−ΔG−1+δG=n−Δ−δ−1≤n−1.Corollary 4.
If1≤δG≤ΔG≤n−2, ℛ1/2G+ℛ1/2G¯=n−1 if G is regular and γ1/2G=γ1/2G¯=2. Also, ℛ1/2G+ℛ1/2G¯=n−2 if ΔG=δG+1 and γ1/2G=γ1/2G¯=2.Theorem 11.
If1≤δG≤ΔG≤n−2, then ℛ1/2G+ℛ1/2G¯≤n−Δ−δ−γ1/2G+1.Proof.
By Theorem6, ℛ1/2G≤n−ΔG−γ1/2G+1 and ℛ1/2G¯≤n−Δ¯−1=δG. So, ℛ1/2G+ℛ1/2G¯≤n−Δ−δ−γ1/2G+1. Now, we show that if γ1/2G≥3, then either γ1/2G=2 or γ1/2G¯=2.Theorem 12.
If1≤δ≤Δ≤n−2, then either γ1/2G=2 or γ1/2G¯=2.Proof.
Assume thatγ1/2G≥3. Let D=u1,…,uk be a γ1/2-set of G. Let V=V0∪V1∪V2, where V0=D, V2=V−ND, and V1=V−V0∪V2. We claim that γ1/2G¯=2 (as 1≤δG,γ1/2G¯≠1).Case (i):∪i=1kP2ui,D≥2. Select x≠y∈∪P2ui,D. Assume that x∈P2u1,D∩P2u2,D and y∈P2ui1,D∩P2ui2,D, where i1≠i2 (i1,i2 may be the set 1,2). Clearly, D=V0⊂N1¯x∩N1¯y, and V2⊂N1¯D. So, V2−x,y⊂N2¯x∩N2¯y. Let v∈V1. Then v∈N1uj for some j. If j∉1,2, then either v∈N1¯x or v∈N1¯u1 and hence either v∈N1¯x or v∈N2¯x∩N2¯y. If j∈1,2, then either v∈N1¯x or v∈N1¯u3. Thus, if ∪i=1kP2ui,D≥2, x,y is a half-dominating set for G¯.Case (ii):∪i=1kP2ui,D=1. Let ∪P2ui,D=x. Assume that x∈N2u1∩N2u2. Then, x∉N2ui for all i≥3. As P2u3,D=ϕ, P1u3,D≠ϕ. Select y∈P1u3,D. Then, V0⊂N1x¯, and V0−u3⊂N1¯y. V2⊂N2¯x∩N2¯y as V2⊂N2¯u3. Let v≠y∈V1 and v∈N1uj for some j. If j∉1,2, v∈N1x¯. If j∈1,2, say j=1; then either v∈N1y¯ or v∈N1u2¯. Thus, in this case, x,y is a half-dominating set of G¯.Case (iii):P2ui,D=ϕ for all i. Then, P1ui,D≠ϕ for all i. Let x∈P1u1,D, and y∈P1u2,D. Then, u1∈N1¯y, u2∈N1¯x, and ui∈N1¯x∩N1¯y∀i≥3. V2⊂N1¯u3⊂∩N2x¯∩N2¯y. Let v≠x,y∈V1. Then, either v∈N1¯x or v∈N1¯u3. Then, in this case, also x,y is a half-dominating set for G¯. Now it follows that γ1/2G¯=2.Remark 8.
We obtain the following bounds forℛ1/2G+ℛ1/2G¯, using Theorems 7, 8, and 12. If 1≤δG and γ1/2G≥3, then(6)ℛ1/2G+ℛ1/2G¯≤2Δ+δ,ifγ1/2G≤ΔG,Δ+δ+1,ifγ1/2G−1=ΔG,Δ+δ,ifΔG<γ1/2G−1.
Finally, we conclude this paper with the following remark on the bounds for the productℛ1/2G⋅ℛ1/2G¯.Remark 9.
Letk≥2 be an integer. If x+y=k, where x and y are nonnegative integers, then the product xy attains the maximum value if x=y=k/2 when k is even and x,y=k−1/2,k+1/2 when k is odd. Thus,(7)maxx+y=kxy=k22,ifkis even,k−1k+14,ifkis odd.
Also, if2≤k1≤k2, then maxx+y=k1xy≤maxx+y=k2xy. As for any graph ℛ1/2G+ℛ1/2G¯≤n−1, where VG=n, we have an upper bound for the product ℛ1/2G⋅ℛ1/2G¯. In fact, ℛ1/2G⋅ℛ1/2G¯≤n−1/22,ifnis odd,nn−2/4,ifnis even.
There are graphsG for which the product ℛ1/2G⋅ℛ1/2G¯ attains this upper bound.
Ifn≥5 is odd and G is a n−1/2-regular graph, then ℛ1/2G⋅ℛ1/2G¯=n−1/22 and ℛ1/2G=ℛ1/2G¯=2. Note that Harary graphs H2n+1,n satisfy these properties. If n≥3, then, in this case, Harary graph H2n,n−1 can be considered as an example.


## 5. Conclusion

In this paper, we introduced the conceptℛ1/2G, the reinforcement number of a graph G with respect to the 1/2-dominating number of G. Also, we studied various upper bounds for ℛ1/2G and exhibited that these bounds are sharp. Furthermore, we obtained Nordhaus–Gaddum-type bounds for the sum ℛ1/2G+ℛ1/2G¯ and the product ℛ1/2G⋅ℛ1/2G¯.



---

*Source: 6689816-2021-04-14.xml*