# Some Properties of Double Roman Domination

Authors: Hong Yang; Xiaoqing Zhou
Journal: Discrete Dynamics in Nature and Society
 (2020)

---

## Abstract

Adouble Roman dominating function on a graph G is a function f:VG⟶0,1,2,3 satisfying the conditions that every vertex u for which fu=0 is adjacent to at least one vertex v for which fv=3 or two vertices v1 and v2 for which fv1=fv2=2 and every vertex u for which fu=1 is adjacent to at least one vertex v for which fv≥2. The weight of a double Roman dominating function f is the value fV=∑u∈Vfu. The minimum weight of a double Roman dominating function on a graph G is called the double Roman domination numberγdRG of G. A graph with γdRG=3γG is called a double Roman graph. In this paper, we study properties of double Roman domination in graphs. Moreover, we find a class of double Roman graphs and give characterizations of trees with γdRT=γRT+k for k=1,2.


---

## Body

## 1. Introduction

In this paper, we shall only consider graphs without multiple edges or loops. LetG be a graph, v∈VG, and the neighborhood of v in G is denoted by Nv. That is to say, Nv=uuv∈EG,u∈VG. The closed neighborhood Nv of v in G is defined as Nv=v∪Nv. The complementary graph of G is denoted by G¯. A vertex of degree one is called a leaf. A graph is trivial if it has a single vertex. The degree of a vertex v is denoted by dv, i.e., dv=Nv. Denote by Kn, Pn, and Cn the complete graph, path, and cycle on n vertices, respectively. The maximum degree and the minimum degree of a graph are denoted by ΔG and δG, respectively. For a set S⊆VG, the graph induced by S is denoted by GS. Let e∈EG, and we denote by G/e the graph obtained from G by contracting the edge e. For an edge e∈EG, we denote by G−e the graph obtained from G by deleting e.A subsetD of the vertex set of a graph G is a dominating set if every vertex not in D has at least one neighbour in D. The domination number γG is the minimum cardinality of a dominating set of G.The domination and its variations of graphs have attracted considerable attention [1, 2]. Many varieties of dominating sets are listed in the book Fundamentals of Domination in Graphs [3]. However, Roman domination and double Roman domination are not listed in this book. Roman domination and double Roman domination appear to be a new variety of interest [4–11].A Roman dominating function (RDF) of a graphG is a function f:VG⟶0,1,2 such that every vertex u for which fu=0 is adjacent to at least one vertex v for which fv=2. The weight wf of a Roman dominating function f is the value wf=∑u∈VGfu. The minimum weight of a Roman dominating function on a graph G is called the Roman domination numberγRG of G. An RDF f of G with wf=γRG is called a γRG function.Adouble Roman dominating function (DRDF) on a graph G is a function f:VG⟶0,1,2,3 satisfying the condition that every vertex u for which fu=0 is adjacent to at least one vertex v for which fv=3 or two vertices v1 and v2 for which fv1=fv2=2 and every vertex u for which fu=1 is adjacent to at least one vertex v for which fv≥2. The weight wf of a double Roman dominating function f is the value wf=∑u∈VGfu. The minimum weight of a double Roman dominating function on a graph G is called the double Roman domination numberγdRG of G. A DRDF f of G with wf=γdRG is called a γdRG function. We denote by wSf the weight of a double Roman dominating function f in S⊆VG, i.e., wSf=∑x∈Sfx.Beeler et al. [12] initiated the study of the double Roman domination in graphs. They showed that 2γG≤γdRG≤3γG and defined a graph G to be double Roman if γdRG=3γG. Moreover, they suggest to find double Roman graphs.In this paper, we study properties of double Roman domination in graphs and show that the double Roman domination problem is NP-complete for bipartite graphs. Moreover, we find a class of double Roman graphs and give characterizations of trees withγdRT=γRT+k for k=1,2.


## 2. Properties of Double Roman Domination

Proposition 1 (see [12]).
In a double Roman dominating function of weightγdRG, no vertex needs to be assigned the value 1.By Proposition1, when we consider a γdRG function, we assume no vertex has been assigned the value 1.Proposition 2 (see [12]).
(i)
LetG be a graph and f=V0,V1,V2 be a γRG function. Then, γdRG≤2V1+3V2.(ii)
For any graphG, γdRG≤2γRG with equality if and only if G=Kn¯.Proposition 3 (see [12]).
(i)
For every graphG, γRG<γdRG.(ii)
Iff=V0,∅,V2,V3 is any γdRG function, then γRG≤2V2+V3=γdRG−V3.The following result is immediate.Proposition 4.
For any graphG, γdRG≥3VG/ΔG+1.Proof.
The desired inequality obviously holds ifΔG≤1. In order to prove the proposition for ΔG≥2, we introduce the discharging approach. Let f=V0,∅,V2,V3 be a γdRG function. The initial charge of every vertex v∈VG is set to be sv=fv. We apply the discharging procedure defined by applying the following rule.
For each vertexv∈V3, we send 3/dv+1 charge to each adjacent vertex in V0. Then, the final charge of v is satisfying with sv=3/dv+1≥3/ΔG+1.
For each vertexv∈V2, we send 2/dv+1−3/dvΔG+1=2ΔG−1/dvΔG+1≥2ΔG−1/ΔGΔG+1 charge to each adjacent vertex in V0. Then, the final charge of v is satisfying with sv=3/dv+1≥3/ΔG+1.
For each vertexv∈V0, by the definition of double Roman domination, v has a neighbor assigned 3 or two vertices u1andu2 assigned 2. Due to the discharging rule above, if v has a neighbor u assigned 3, v receives charge from u. We have sv≥3/ΔG+1.
Ifv has two vertices u1andu2 assigned 2, v receives charge from u1andu2. We have sv≥4ΔG−2/ΔGΔG+1≥3/ΔG+1. Thus, γdRG=∑v∈VGfv=∑v∈VGsv≥3VG/ΔG+1. The proof is complete.Proposition 5.
LetG be a graph. If γRG+1=γdRG and f=V0,∅,V2,V3 is a γdRG function,(i)
thenV3≤1(ii)
ifV3=1, then V2=0 and there exists a vertex v with degree VG−1.Proof.
(i)
By Proposition3, we have γRG≤γdRG−V3=γRG+1−V3. So we have V3≤1.(ii)
IfV3=1, let V3=v and H=GVG−NV3. We have the following claim.Claim 1.
H is empty.Proof.
Otherwise, any vertex inH assigned with 0 has at least two vertices assigned with 2. Let w be a vertex in H assigned with 2, we consider a function f′ with f′w=1, f′v=2, and f′x=fx for any x∈VG−v,w. Then, f′ is an RDF of G with weight γdRG−2. So γRG≤γdRG−2, a contradiction.
SinceH is empty, we have v as a vertex with degree VG−1. Now, we have γdRG=3 and γRG=2, and so the result holds.Theorem 1.
For every graphG on n vertices without isolated vertex, γdRG≤3n−3n/21+δGe1/δG.Proof.
Clearly, we haveδG≥1. We select a subset S of VG, where each vertex is selected with probability p independently. Let T=VG−NS, we consider a function f:VG⟶0,2,3 with fx=3 for x∈S, fx=2 for x∈T, and fx=0 for other vertex x. Then, f is a DRDF of G. We have γdRG≤3S+2T. When we consider the expectation, we also have γdRG≤E3S+2T=3ES+2ET. First, it is clear that ES=np. For each vertex with degree dx, if neither x nor any neighbor is selected, then x∈T. So we have Px∈T=1−p1+dx, and thus, ET≤n1−p1+δG. Consequently, γdRG≤3np+2n1−p1+δG. Let Fp=3np+2n1−p1+δG. By Fp=3np−2n1+δG1−pδG=0, the maximum of F is given by Fmax=3n−3n/21+δGe1/δG at p=1−3/21+δGe1/δG∈0,1. Thus, γdRG≤3n−3n/21+δGe1/δG.
IfG is a graph with some isolated vertices, then δG=0. Let W be the set of isolated vertices of G and let G′=G−W. Therefore, δG′≥1. Because all isolated vertices must be assigned 3, it is easy to prove that γdRG≤3n−3n′/21+δG′e1/δG′, where n′=VG′.Proposition 6.
IfG is a connected graph of order n, then γdRG+1=2γRG if and only if there exists a vertex v of degree n+1−γdRG+1/2 in G.Proof.
(⇒) Let f=V0,V1,V2 be a γRG function with minimum V1. Then, we have V1 being independent. Together with Proposition 2, we have γdRG≤2V1+3V2≤2V1+4V2=2γRG=γdRG+1. Then, we have V2≤1. If V2=0, we have V0=0, and thus γRG=n=V1. Since V1 is independent, it is impossible. If V2=1, we have γdRG=2V1+3V2<2V1+4V2=2γRG=γdRG+1. Let V2=v, V0=Nv, and V1=VG−V0−V2. Then, we have γRG=n−1−dv+2 and so dv=n+1−γRG=n+1−γdRG+1/2.(⇐) By Proposition 2 (ii), we have γdRG+1≤2γRG for a connected graph G. Assume G contains a vertex v of degree n+1−γdRG+1/2 in G. Let V2=v, V0=Nv, and V1=VG−V0−V2. Then, f=V0,V1,V2 is a γRG function and so γRG≤V1+2V2=γdRG+1/2. Hence, γdRG+1≥2γRG.
Letℱ be the family of connected graphs G such that for any γdRG function f=V0,∅,V2,V3, we have V3=0.Proposition 7.
LetG∈ℱ, then(i)
G contains no strong support vertex(ii)
iffu=fv=2 for an edge uv∈EG, then G−e∈ℱ and G/e∈ℱ.Proof.
(i)
Supposev be a strong support vertex, then there exist two leaves x,y∈Nv. Since fv≠3, we have fx=fy=2. Now consider the function f′ with f′z=0 for any z∈Lv, f′v=3, and f′z=fz for any z∈VG∖Lv. Then, f′ is a DRDF of G with fewer weight than f, a contradiction.(ii)
Iffu=fv=2 for an edge uv∈EG, we have f as also a DRDF of G−e. So γdRG−e≤wf=γdrG. Since for any graph G, we have γdRG−e≥γdRG, so γdRG−e=γdRG. Suppose to the contrary that there exists a γdRG−e function such that fv=3 for a vertex v∈VG−e. Then, f is also a γdRG function, contradicting with V3=0. For the graph G/e, the proof is similar.Lemma 1.
LetG be a graph on n≥4 vertices, then γdRG=4 if and only if G contains a complete bipartite graph K2,n−2 as a subgraph and ΔG≤n−2.Proof.
⇒ If γdRG=4, then no vertex is assigned with 3 and thus we have two vertices vandw assigned with 2 and the others 0. Also, each vertex 0 must be adjacent to both v and w. Therefore, G contains a complete bipartite graph K2,n−2 as a subgraph. Since γdRG>3, we have ΔG≤n−2.⇐ If G contains a complete bipartite graph K2,n−2 with partitions X,Y (X=2,Y=n−2) as a subgraph and ΔG≤n−2. Then, let fx=2 for any x∈X and fx=0 for x∈Y. Then, f is a DRDF of G and so γdRG≤4. Since G contains no vertex with degree VG−1, we have γdRG≥4.
Note thatΔG≥n−2 if G contains a complete bipartite graph K2,n−2 as a subgraph. Thus, ΔG≤n−2 can be replaced with ΔG=n−2 in the lemma.Theorem 2.
LetG be a graph on n≥3 vertices, then 8≤γdRG+γdRG¯≤2n+3. Furthermore, equality holds in the upper bound if G or G¯ is Kn.Proof.
IfG is a graph on n≥3 vertices, we have γdRG≥3, and if γdRG=3, then G has a vertex with degree n−1. But its complement is neither a star nor a graph G with γdRG=4 (see the graph stated in Lemma 1). So we have γdRG¯≥5 and thus, γdRG+γdRG¯≥8. If G is a star, then γdRG¯=5 and so the lower bound is attainable.
Letv be a vertex with maximum degree ΔG; consider a function f with fv=3, fx=0 for any x∈Nv, and fx=2 for x∈VG−Nx. Then, f is a DRDF of G and so γdRG≤wf=2n−2ΔG+1. Since ΔG¯+δG=n−1, we have γdRG¯≤2n−2ΔG¯+1=2δG+3. Therefore, γdRG+γdRG¯≤2n+4−2ΔG+2δG≤2n+4. It can be seen that if γdRG+γdRG¯=2n+4, then ΔG=δG. Hence, G is k-regular for some k. By symmetry, we may assume that k≤n−1/2. Then, if γdRG+γdRG¯=2n+4, we have γdRG=2n−2k+1 and γdRG¯=2k+3. Let v∈VG. If Nu∩Nv≤k−2 for some u∈VG−Nv, then f=Nv∪Nu,∅,VG−Nu−Nv,u,v is a DRDF of G with fewer weight than 2n−2k+1, a contradiction. Therefore, each vertex not in Nv has at least k−1 neighbors in Nv. Analogously, each vertex in Nv has at most 2 neighbors outside Nv. Then, we have k−1n−k−1≤2k. Since k≤n−1/2, we have k≤2+2/k−1. If k=3, then n=7. This is impossible. If k=2, then n∈5,6,7. If G=C5, we have γdRG=γdRG¯=6, and so γdRG+γdRG¯≠2n+4, a contradiction. If G=C6, we have γdRG=γdRG¯=6, and so γdRG+γdRG¯≠2n+4, a contradiction. If G=C7, we have γdRG=8andγdRG¯=6, and so γdRG+γdRG¯≠2n+4, a contradiction. If k=1, then G=n/2K2, and we have γdRG=3n/2 and γdRG¯=4, and so γdRG+γdRG¯≠2n+4, a contradiction. Therefore, we conclude that 8≤γdRG+γdRG¯≤2n+3. If G=Kn, then γdRG=3andγdRG¯=2n and thus the upper bound is attainable.


## 3. Some Double Roman Graphs

TheCartesian product of graphs G and H is the graph G□H with vertex set G×H and x1,x2y1,y2∈EG□H whenever x1y1∈EG and x2=y2, or x2y2∈EH and x1=y1. The Cartesian product is commutative and associative, having the trivial graph as a unit (cf. [13]).Letf be a double Roman dominating function of Cm□Cn, and we write Vif=v∈VCm□Cnfv=i for i∈0,1,2,3. When no confusion arise, we simply write Vif as Vi. We use fi,j to denote the value fv for v=i,j∈VCm□Cn. Let xi be the weight of Ci, i.e., xi=∑x∈Cifx.Theorem 3.
Letm,n≥1. Then, the Cartesian product graphs C5m□C5n are double Roman.Proof.
The lower bound follows from Proposition4. Let VC5m□C5n=vij:0≤i≤5m−1,0≤j≤5n−1, V1=V2=∅, V3=v5i5j+2, v5i+15j, v5i+25j+3, v5i+35j+1, v5i+45j+4, 0≤i≤m−1, 0≤j≤n−1, and V0=NV3. Then, NV3=VC5m□C5n and so f=V0,V1,V2,V3 is a DRDF of C5m□C5n with weight 15mn and we have γdRC5m□C5n≤15mn. Since γC5m□C5n=5mn, we have C5m□C5n is double Roman.


## 4. TreesT with γdRT=γRT+k

Theorem 4.
IfT is a tree, then γRT+1=γdRT if and only if T is a star K1,s for s≥1.Proof.
⇐ If T is a star K1,s for s≥1, it is clear that γdRT=3 and γRT=2, and the theorem holds.⇒ By Proposition 3, we have V3≤1. If V3=1, by Proposition 5, we have T is a star K1,s for some s≥1. If V2=0, then each vertex in T is assigned 2 or 0. Since T is a tree, T has a least two leaves vandw and fv=fw=2. If vandw are adjacent to the same vertex x, then we can obtain a DRDF of T with fewer weight by changing fx to 3 and fvandfw to 0 and obtaining a contradiction. If vandw are adjacent to different vertices, we consider a function f′ with f′w=1, f′v=1, and f′x=fx for any x∈VT−v,w. Then, f′ is an RDF of T with weight γdRT−2. So γRT≤γdRT−2, a contradiction.
For a positive integert, a wounded spider is a star K1,t with at most t−1 of its edges subdivided. In a wounded spider, a vertex of degree t will be called the head vertex, and the vertices at distance two from the head vertex will be the foot vertices.Theorem 5.
IfT is a tree, then γRT+2=γdRT if and only if T is a wounded spider with only one foot or T is obtained by adding an edge between two stars K1,s and K1,t for s,t≥2.Proof.
⇐ If T is a wounded spider with only one foot, it is clear that γdRT=5 and γRT=3, and the theorem holds. If T is a tree obtained by adding an edge between two stars K1,s and K1,t for s,t≥2, then γdRT=6 and γRT=4, and the theorem holds.⇒ By Proposition 3, we have V3≤2. If V3=2, let V3=v,w and H=GVG−Nw−Nv. Similar to the proof of Theorem 5, we have H as empty. Otherwise, there exists a vertex u in H assigned with 2. Now, we change the function values of v,w,u from 3,3,2 to 2,2,1, respectively, and obtain an RDF of T with weight γdRT−3, a contradiction. In this case, T is a tree obtained by adding an edge between two stars K1,s and K1,t for s,t≥2. If V3=1, let V3=v and H=GVG−Nv. Then, H has at most one connected component. Otherwise, we can make a vertex in each connected component to change the function values including the vertex v to obtain an RDF of T with weight γdRT−3. Since H contains no vertex assigned with 3, then H is not a star with at least two leaves. We claim that the leaves of H are at most two. Otherwise, we change the function values of v and choose two leaves to obtain an RDF of T with weight γdRT−3. Therefore, H is a path on at least four vertices. In this case, we can obtain an RDF of T with weight at most γdRT−3, a contradiction. Therefore, T is a wounded spider with only one foot.



---

*Source: 6481092-2020-08-14.xml*