EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS Vol. 13, No. 3, 2020, 529-548 ISSN 1307-5543 – www.ejpam.com Published by New York Business Global More on Perfect Roman Domination in Graphs Leonard Mijares Paleta1,∗, Ferdinand P. Jamil2 1 Department of Mathematics, College of Science and Mathematics, University of Southern Mindanao, Kabacan 9407, North Cotabato, Philippines 2 Department of Mathematics and Statistics,College of Science and Mathematics. Center for Graph Theory, Algebra and Analysis, Premier Research of Institute of Science and Mathematics, Mindanao State University-Iligan Institute of Technology, 9200 Iligan City, Philippines Abstract. A perfect Roman dominating function on a graph G = (V (G), E(G)) is a function f : V (G) → {0, 1, 2} for which each u ∈ V (G) with f(u) = 0 is adjacent to exactly one vertex v ∈ V (G) with f(v) = 2. The weight of a perfect Roman dominating function f is the value ωG(f) = ∑ v∈V (G) f(v). The perfect Roman domination number of G is the minimum weight of a perfect Roman dominating function on G. In this paper, we study the perfect Roman domination numbers of graphs under some binary operations. 2020 Mathematics Subject Classifications: 05C22, 05C69,05C76 Key Words and Phrases: Roman dominating function, perfect Roman dominating function, Roman domination number, perfect Roman domination number 1. Introduction Throughout this paper, all graphs considered are finite, simple and undirected. Let G = (V (G), E(G) be a graph. The sets V (G) and E(G) are the vertex set and edge set, respectively, of G. For S ⊆ V (G), |S| is the cardinality of S. In particular, |V (G)| is called the order of G. For notation and terminology not given here, see [5]. Vertices u and v of G are neighbors if uv ∈ E(G). The open neighborhood of v refers to the set NG(v) consisting of all neighbors of v. The closed neighborhood of v is the set NG[v] = NG(v) ∪ {v}. The degree of v, denoted degG(v), refers to the value |NG(v)|, and we define ∆(G) = max{degG(v) : v ∈ V (G)}. Vertex v is an endvertex if degG(v) = 1, and End(G) is the set of all endvertices of G. Vertex v is an isolated vertex if degG(v) = 0. We denote by Iso(G) the set of all isolated vertices of G. For S ⊆ V (G), NG(S) = ∪v∈SNG(v), and NG[S] = S ∪NG(S). ∗Corresponding author. DOI: https://doi.org/10.29020/nybg.ejpam.v13i3.3763 Email addresses: leonard.paleta@g.msuiit.edu.ph (L. Paleta), ferdinand.jamil@g.msuiit.edu.ph (F. Jamil) https://www.ejpam.com 529 c© 2020 EJPAM All rights reserved. L. Paleta, F. Jamil / Eur. J. Pure Appl. Math, 13 (3) (2020), 529-548 530 Let G and H be graphs with disjoint vertex sets. The disjoint union of G and H is the graph G∪H with V (G∪H) = V (G)∪V (H) and E(G∪H) = E(G)∪E(H). The join of G and H is the graph G+H with vertex set V (G)∪V (H) and edge set E(G)∪E(H)∪{uv : u ∈ V (G), v ∈ V (H)}. The corona of G and H is the graph G ◦H obtained by taking one copy of G and |V (G)| copies of H, and then joining the ith vertex of G to every vertex in the ith copy of H. The edge corona of G and H is the graph G � H obtained by taking one copy of G and |E(G)| copies of H and joining each of the end vertices u and v of each edge uv of G to every vertex of the copy Huv of H. The composition G[H] of G and H is the graph with V (G[H]) = V (G) × V (H) and (u, v)(u′, v′) ∈ E(G[H]) if and only if either uu′ ∈ E(G) or u = u′ and vv′ ∈ E(H). The complementary prism, denoted GG, is the graph formed from the disjoint union of G and its complement G by adding a perfect matching between corresponding vertices of G and G. For the complementary prism, V (GG) = V (G) ∪ V (G) and E(GG) = E(G) ∪E(G) ∪ {vv : v ∈ V (G)}, where v is the vertex in G corresponding to v ∈ V (G) in the perfect matching. A subset S ⊆ V (G) is a dominating set of G if NG[S] = V (G). The minimum cardinality of a dominating set is the domination number of G, denoted by γ(G). For more details and results on domination number, we refer to [4, 9–11, 13]. In particular, if γ(G) = 1 and NG[v] = V (G), then v is said to be a dominating vertex of G. In this case, Dom(G) denotes the set of all dominating vertices of G. Any dominating set of G of cardinality γ(G) is called γ-set of G. A dominating set S of G is a perfect dominating set if for every v ∈ V (G) \ S, there exists exactly one u ∈ S for which uv ∈ E(G) [16]. The minimum cardinality of a perfect dominating set is the perfect domination number of G, which is denoted by γP (G). Since perfect dominating sets are dominating sets, γ(G) ≤ γP (G) for any graph G. A Roman dominating function on G is a function f : V (G) → {0, 1, 2} satisfying the condition that for each u ∈ V (G) for which f(u) = 0, there exists v ∈ V (G) such that f(v) = 2 and uv ∈ E(G). The weight of f is the value ωG(f) = ∑ v∈V (G) f(v). The Roman domination number of G, denoted by γR(G), is the minimum weight of a function f on G. We refer to [2, 3, 7, 8, 12, 17, 18] for the history, introduction, importance and for some of the recent developments of the study of Roman domination in graphs. Customarily, we write f = (V0, V1, V2) for a Roman dominating function f on G, where Vk = {v ∈ V (G) : f(v) = k}. With this convention, ωG(f) = |V1|+ 2|V2| and V1 ∪ V2 is a dominating set of G. In [8], it is known that for any graph G, γ(G) ≤ γR(G) ≤ 2γ(G). A perfect Roman dominating function (or PRD-function) on G is a Roman domination function f = (V0, V1, V2) on G such that for each u ∈ V0 there exists exactly one v ∈ V2 for which uv ∈ E(G). In other words, a PRD-function on G is a colouring of the vertices of G using colours 0, 1 and 2 such that each vertex coloured 0 is adjacent to exactly one vertex coloured 2. The perfect Roman domination number of G, denoted by γPR(G), is the minimum weight of a PRD-function on G. A PRD-function f with ωG(f) = γPR(G) is called γPR -function of G. The perfect Roman domination, a variation of the Roman domination, was introduced and first investigated in 2018 by Henning et al. [15], particularly in trees. It is further studied in [14] for regular graphs. More recent studies on the concept include [1, 19, 20]. L. Paleta, F. Jamil / Eur. J. Pure Appl. Math, 13 (3) (2020), 529-548 531 In this present paper, we continue the study of perfect Roman domination, specifically on the join, corona, complementary prism, edge corona and composition of graphs. The following bounds are established in the referred articles above. Theorem 1.1. (i)[15] If T is a tree of order n ≥ 3, then γPR(T ) ≤ 4 5n; (ii) [14] If G is a k-regular graph of order n with k ≥ 4, then γPR(G) ≤ ( k2+k+3 k2+3k+1 ) n; (iii) [19] If G is a graph of order n, then γPR(G) ≤ n+ 1−∆(G). (iv) [19] For paths Pn and cycles Cn on n ≥ 3 vertices, γPR(Pn) = γPR(Cn) = d2n3 e. For convenience, we adapt the symbol PRD(G) to denote the set of all perfect Roman dominating functions on the graph G. 2. Results The following proposition plays an important role in proving the desired results. Proposition 2.1. If f = (V0, V1, V2) is a γPR -function of G, then |NG(v) ∩ V2| 6= 1 for each v ∈ V1. Proof : Suppose that there exists v ∈ V1 for which |NG(v)∩V2| = 1. Consider, in particular, the function f∗ = (V ∗0 , V ∗ 1 , V ∗ 2 ) given by f∗(v) = 0 and f∗(x) = f(x) for all x 6= v. We have f∗ ∈ PRD(G) with V ∗0 = V0∪{v}, V ∗1 = V1\{v} and V ∗2 = V2. Thus, ωG(f∗) = γPR(G)−1, a contradiction. � Proposition 2.2. For a nontrivial connected graph G of order n, max{2, γ(G)} ≤ γPR(G) ≤ min{n+ 1−∆(G), 2γP (G)}. Proof : Since a perfect Roman domination is a Roman domination, γ(G) ≤ γPR(G). Let f = (V0, V1, V2) be a γPR -function of G. If V0 = ∅, then γPR(G) = n ≥ 2. On the other hand, if V0 6= ∅, then V2 6= ∅ so that γPR(G) ≥ 2|V2| ≥ 2. By Theorem 1.1(iii), γPR(G) ≤ n + 1 −∆(G). Now, let S ⊆ V (G) be a γP -set of G. Then f = (V0, V1, V2) ∈ PRD(G), where V0 = V (G) \ S, V1 = ∅ and V2 = S. Therefore, γPR(G) ≤ 2|S| = 2γP (G). � Observe that γPR(Ck) = 4 = k + 1−∆(Ck) < 2γP (Ck) for k = 5 and γPR(C3n) = 2n = 2γP (C3n) < (3n+ 1)−∆(C3n) for all n ≥ 2. Therefore, the upper bound of the inequality in Proposition 2.2 is sharp and may be determined by exactly one of n + 1 −∆(G) and 2γP (G). The inequality, however, can also be strict. To see this, note that γPR(C7) = 5 < min{(7 + 1)−∆(C7), 2γ P (C7)}. Corollary 2.3. Let G be a connected graph of order n ≥ 2. Then (i) [19] γPR(G) = 2 if and only if γ(G) = 1. L. Paleta, F. Jamil / Eur. J. Pure Appl. Math, 13 (3) (2020), 529-548 532 (ii) γPR(G) = n if and only if n = 2. (iii) [19] γPR(G) = 3 if and only if ∆(G) = n− 2. (iv) If G is the complete multipartite graph Kr1,r2,...,rm, where 2 ≤ r1 ≤ r2 ≤ . . . ≤ rm, then γPR(G) = { min{r1 + 1, 4}, if m = 2; r1 + 1, if m ≥ 3. Proof : Clearly, if γ(G) = 1, then γP (G) = 1 and the inequalities in Proposition 2.2 imply that γPR(G) = 2. Now, suppose that γPR(G) = 2, and let f = (V0, V1, V2) be a γPR -function of G. If V2 = ∅, then V (G) = V1 and γPR(G) = n = 2. Since G is connected, G = P2 and γ(G) = 1. If V2 6= ∅, then V1 = ∅ and V2 = {v} with NG[v] = V (G). This means that γ(G) = 1. This proves (i). If n = 2, then G = P2 and γPR(G) = 2 = n. Conversely, suppose that n ≥ 3. Pick v ∈ V (G) such that degG(v) = ∆(G) ≥ 2. Define on G f(x) =  2, if x = v; 0, if x ∈ NG(v); 1, else. Then f ∈ PRD(G) and ω(f) = n− (∆(G)− 1) < n, a contradiction. Thus, if γPR(G) = n, then n = 2. We have proved (ii). If ∆(G) = n − 2, then Proposition 2.2 implies that 2 ≤ γPR(G) ≤ 3. Since γ(G) ≥ 2, γPR(G) = 3 by (i). Conversely, suppose that γPR(G) = 3. By (i), γ(G) ≥ 2 so that ∆(G) ≤ n − 2, and by (ii), n ≥ 4. Let f = (V0, V1, V2) be a γPR -function on G. If V2 = ∅, then V1 = V (G) and γPR(G) = n ≥ 4, a contradiction. Thus, |V2| = |V1| = 1, say V1 = {u} and V2 = {v}. This means that V (G)\{u, v} ⊆ V0. Further, by Proposition 2.1, uv /∈ E(G). Accordingly, degG(v) = n− 2. Therefore, ∆(G) ≥ n− 2. This proves (iii). Suppose that G is the complete multipartite graph described in (iv). Then ∆(G) = n − r1. Suppose first that m = 2. Then γ(G) = γP (G) = 2. By Proposition 2.2, γPR(G) ≤ min{r1 + 1, 4}. Also, by (i), γPR(G) ≥ 3. If r1 = 2, then γPR(G) = 3 = r1 + 1. On the other hand, if r1 ≥ 3, then γPR(G) = 4 ≥ r1 + 1. Now, assume that m ≥ 3. By (ii), γPR(G) < n. Let f = (V0, V1, V2) be a γPR -function on G. Then |V2| = 1, say V2 = {v}. Since f is a γPR -function, v ∈ U , where U is the partite set of G with |U | = r1. More precisely, f(v) = 2, f(x) = 1 for all x ∈ U \ {v} and f(x) = 0 for all x ∈ V (G) \ U . Thus, γPR(G) = ωG(f) = r1 + 1. This proves (iv). � Proposition 2.4. [19] Let G1, G2, . . ., Gk be the components of G. Then γPR(G) =∑k j=1 γ P R(Gj). Proposition 2.4 and Corollary 2.3(ii) yield the following corollary. L. Paleta, F. Jamil / Eur. J. Pure Appl. Math, 13 (3) (2020), 529-548 533 Corollary 2.5. Let G be a graph of order n. Then γPR(G) = n if and only if G = ∪kj=1Gj, where Gj ∈ {K1,K2} for all j = 1, 2, . . . , k. Corollary 2.6. Let G be a graph of order n. Then γ(G) = γPR(G) if and only if G = Kn. Proof : If G = Kn, then γ(G) = n and by Corollary 2.5, γPR(G) = n. Conversely, suppose that γ(G) = γPR(G), and let f = (V0, V1, V2) be a γPR -function of G. Note that if V2 6= ∅, then γ(G) ≤ |V1| + |V2| < γPR(G), a contradiction. Thus, V2 = V0 = ∅ and γPR(G) = n. This means that γ(G) = n and, thus, G = Kn. � 2.1. On the join of graphs By Corollary 2.3(i), γPR(G+Kn) = 2 for all graphs G and for all n ≥ 1. The following theorem characterizes all PRD-functions on the join of nontrivial con- nected graphs. Theorem 2.7. Let G and H be any nontrivial connected graphs and f = (V0, V1, V2). Then f ∈ PRD(G+H) if and only if one of the following holds: (i) V2 ⊆ V (G) and one of the following holds: (a) V0 ⊆ V (G), V (H) ⊆ V1 and (V0, V1 ∩ V (G), V2) ∈ PRD(G); (b) V0 ∩ V (H) 6= ∅ and V2 = {v} for which V0 ∩ V (G) ⊆ NG(v). (ii) V2 ⊆ V (H) and one of the following holds: (a) V0 ⊆ V (H), V (G) ⊆ V1 and (V0, V1 ∩ V (H), V2) ∈ PRD(H); (b) V0 ∩ V (G) 6= ∅ and V2 = {v} for which V0 ∩ V (H) ⊆ NH(v). (iii) A1 = V2 ∩ V (G) 6= ∅ and A2 = V2 ∩ V (H) 6= ∅ and the following holds: (a) If V0 ∩ V (G) 6= ∅, then |A2| = 1 and (V0 ∩ V (G)) ∩NG(A1) = ∅; (b) If V0 ∩ V (H) 6= ∅, then |A1| = 1 and (V0 ∩ V (H)) ∩NH(A2) = ∅. Proof : Assume that f is a perfect Roman dominating function on G + H. We consider three cases: Case 1: Suppose that V2 ⊆ V (G). If V0 ⊆ V (G), then V (H) ⊆ V1 and the restriction f |V (G) = (V0, V1 ∩ V (G), V2) of f on G is a perfect dominating function on G. Suppose that V0 ∩ V (H) 6= ∅. Then, |V2| = 1, say V2 = {v}. Necessarily, V0 ∩ V (G) ⊆ NG(v). Case 2: Similarly, if V2 ⊆ V (H), then either (ii)(a) or (ii)(b) holds. Case 3: Assume that V2 intersects both V (G) and V (H), and A1 = V2 ∩ V (G) and A2 = V2∩V (H). Suppose that V0∩V (G) 6= ∅, and let v ∈ V0∩V (G). Since A2 ⊆ NG+H(v), |A2| = 1 and v /∈ NG(A1). Since v is arbitrary, (iii)(a) holds. Similarly, (iii)(b) holds. Conversely, suppose that (i)(a) holds for f , and let w ∈ V0. Then w ∈ V (G) and there exists a unique u ∈ V2 for which uw ∈ E(G). Since V (H) ⊆ V1, u is unique in V (G+H) for L. Paleta, F. Jamil / Eur. J. Pure Appl. Math, 13 (3) (2020), 529-548 534 which uw ∈ E(G+H). This means that f ∈ PRD(G+H). Suppose that (i)(b) holds for f , and let w ∈ V0. Whether w ∈ V (G) or w ∈ V (H), v is a unique element in V2 for which wv ∈ E(G + H). Thus, f ∈ PRD(G + H). Similarly, if (ii) holds, the same conclusion is attained for f . Suppose now that (iii) holds for f . Let v ∈ V0. If v ∈ V (G), then by condition (a), A2 = {u} for some u ∈ V (H) and NG+H(v) = {u}. Similarly, if v ∈ V (H), then A1 = {u} for some u ∈ V (G) and NG+H(v) = {u}. Accordingly, f ∈ PRD(G+H). � We now use Theorem 2.7 to prove the following result which is also provided in [19]. Corollary 2.8. [19] Let Gand H be nontrivial connected graphs of orders m and n, re- spectively. Then γPR(G+H) = min{4 + δ(G) + δ(H),m+ 1−∆(G), n+ 1−∆(H)}. Proof : Let α = min{4 + δ(G) + δ(H),m + 1 −∆(G), n + 1 −∆(H)}. Let v ∈ V (G) for which degG(v) = ∆(G). Define f = (V0, V1, V2) on G+H by f(x) =  2, if x = v; 0, if x ∈ V (H) ∪NG(v); 1, else. Since f satisfies condition (i)(b) of Proposition 2.7, f = (V0, V1, V2) ∈ PRD(G+H) with V2 = {v} and V1 = V (G) \NG[v]. Thus, γPR(G+H) ≤ ωG+H(f) = |V (G) \NG[v]|+ 2 = m+ 1−∆(G). Similarly, γPR(G+H) ≤ n+ 1−∆(H). Now, pick u ∈ V (G) and v ∈ V (H) such that degG(u) = δ(G) and degH(v) = δ(H), and define f = (V0, V1, V2) on G+H by f(x) =  2, if x = u, v; 1, if x ∈ NG(u) ∪NH(v); 0, else. Since f satisfies Proposition 2.7 (iii), f ∈ PRD(G + H). Since V2 = {u, v} and V1 = NG(u) ∪NH(v), γPR(G+H) ≤ ωG+H(f) = |NG(u) ∪NH(v)|+ 4 = 4 + δ(G) + δ(H). All of the above show that γPR(G+H) ≤ α. Now, let f = (V0, V1, V2) be a γPR -function of G + H. By Corollary 2.3(ii), since m+ n ≥ 4, V2 6= ∅. Assume A1 = V2 ∩ V (G) 6= ∅. We consider two cases: L. Paleta, F. Jamil / Eur. J. Pure Appl. Math, 13 (3) (2020), 529-548 535 Case 1: Suppose that A2 = V2 ∩ V (H) = ∅. If Proposition 2.7(i)(a) holds for f , then ωG+H(f) ≥ n+ γPR(G) > n ≥ n+ 1−∆(H) ≥ α. On the other hand, if Proposition 2.7(i)(b) holds for f , then ωG+H(f) ≥ 2 + |V (G) \NG[v]| ≥ m+ 1−∆(G) ≥ α. Case 2: Suppose that A2 = V2 ∩ V (H) 6= ∅. If |A1| ≥ 2 and |A2| ≥ 2, then V0 = ∅ and γPR(G + H) > m + n, which is impossible. Assume that |A2| = 1. We consider two subcases. First, suppose that |A1| ≥ 2. Then V0∩V (H) = ∅, and since f is a γPR -function of G + H, V (G) \NG[A1] ⊆ V0 (by Proposition 2.1) and NG(A1) \ A1 ⊆ V1. This means that |V1| ≥ |V (H) \ V2|+ |NG(A1) \A1| so that ωG+H(f) = (n− 1) + |NG(A1) \A1|+ 2|V2| ≥ n+ 5 > n+ 1−∆(H). Finally, suppose that |A1| = 1. Let A1 = {u} and A2 = {v} for some u ∈ V (G) and v ∈ V (H). By Proposition 2.1, f(x) = 0 for all x ∈ V (G+H) \ (NG[u] ∪NH [v]). Thus, ωG+H(f) ≥ 2|A1 ∪A2|+ |NG(u) ∪NH(v)| ≥ 4 + δ(G) + δ(H) ≥ α. All cases above imply that γPR(G+H) ≥ α. � In particular, if m ≥ n, then γPR(Pm + Pn) = { n− 1, if n ≤ 6; 6, if n ≥ 7. and γPR(Cm + Pn) = { n− 1, if n ≤ 7; 7, if n ≥ 8. 2.2. On the corona of graphs Let G and H be connected graphs. Adapting the notation used in [6], for each v ∈ V (G), Hv denotes that copy of H which is joined with v in G ◦H. In case H = {x}, we write V (Hv) = {xv}. Then V (G+H) = ∪v∈V (G)V (Hv + v), where Hv + v = Hv + 〈v〉. It is worth noting that K1 ◦H = H +K1 for any graph H. Theorem 2.9. For nontrivial connected graphs G of order n, γPR(G ◦K1) = min{ωG(f) + n− |V2| : f = (V0, V1, V2) ∈ PRD(G)}. In particular, γPR(Kn ◦K1) = n+ 1. Proof : Write H = {x}, and put α = min{ωG(f) + n− |V2| : f = (V0, V1, V2) ∈ PRD(G)}. Let f = (V0, V1, V2) ∈ PRD(G). Define f∗ = (V ∗0 , V ∗ 1 , V ∗ 2 ) on G ◦K1 by f∗(z) =  f(z), if z ∈ V (G); 1, if z = xv for some v ∈ V0 ∪ V1; 0, if z = xv for some v ∈ V2. L. Paleta, F. Jamil / Eur. J. Pure Appl. Math, 13 (3) (2020), 529-548 536 Then f∗ ∈ PRD(G ◦K1) with V ∗0 = V0 ∪ {xv : v ∈ V2}, V ∗1 = V1 ∪ {xv : v ∈ V0 ∪ V1} and V ∗2 = V2. Moreover, ωG◦K1(f∗) = ωG(f) + n− |V2|. Thus, γPR(G ◦K1) ≤ α. Let f = (V0, V1, V2) be a γPR -function on G ◦ K1, and let A denote the set of all u ∈ V0 ∩ V (G) for which uv /∈ E(G) for all v ∈ V2 ∩ V (G). Then for each u ∈ A, V2 ∩NG◦K1(u) = {xu}. Define f∗ = (V ∗0 , V ∗ 1 , V ∗ 2 ) on G ◦K1 by f∗(z) =  f(z), if z ∈ V (G) \A; 1, if z ∈ A ∪ {xu : u ∈ (V0 ∪ V1) ∩ V (G)}; 0, if z ∈ {xv : v ∈ V2 ∩ V (G)}. Then f∗ ∈ PRD(G ◦ K1) with V ∗0 = ((V0 ∩ V (G)) \A) ∪ {xu : u ∈ V2 ∩ V (G)}, V ∗1 = A ∪ (V1 ∩ V (G)) ∪ {xu : u ∈ (V0 ∪ V1) ∩ V (G)} and V ∗2 = V2 ∩ V (G). Observe that f(u) + f(xu) = 2 = f∗(u) + f∗(xu) for each u ∈ A, and f(u) + f(xu) ≥ f∗(u) + f∗(xu) for each u ∈ V (G) \A. Thus, ωG◦K1(f) = ∑ u∈A (f(u) + f(xu)) + ∑ v∈V (G)\A (f(u) + f(xu)) ≥ ∑ u∈A (f∗(u) + f∗(xu)) + ∑ u∈V (G)\A (f∗(u) + f∗(xu)) = ωG◦K1(f∗). Since f is a γPR -function, ωG◦K1(f) = ωG◦K1(f∗). Moreover, for each u ∈ V ∗0 ∩ V (G), u ∈ (V0 ∩ V (G))\A so that there exists a unique v ∈ V2∩V (G) = V ∗2 such that uv ∈ E(G). This means that the restriction f∗|G of f∗ to G is a perfect Roman dominating function on G. Thus, γPR(G ◦K1) = ωG◦K1(f∗) = ωG(f∗|G) + ∑ v∈V (G) f∗(xv) = ωG(f∗|G) + | (V0 ∪ V1) ∩ V (G)| = ωG(f∗|G) + n− |V ∗2 ∩ V (G)| ≥ α. � It follows from Theorem 2.9 that for all connected graphs G of order n ≥ 2, γPR(G ◦K1) ≤ γPR(G) + n− λ, where λ = max{|V2| : (V0, V1, V2) is a γPR -function on G}, and this bound is sharp. Verify that equality is attained if G is a cycle Cn (n ≥ 3), a path Pn (n ≥ 2), or any graph with γ(G) = 1. Our desired result for more general graphs G and H will follow from the following characterization. L. Paleta, F. Jamil / Eur. J. Pure Appl. Math, 13 (3) (2020), 529-548 537 Theorem 2.10. Let G and H be nontrivial graphs with G connected, and f = (V0, V1, V2). Then f ∈ PRD(G ◦H) if and only if the following holds: (i) For all v ∈ V0 ∩ V (G) either (a) V2∩NG(v) = ∅ and V2∩V (Hv) = {u} with u satisfying V0∩V (Hv) ⊆ NHv(u); or (b) |V2 ∩NG(v)| = 1 and V (Hv) ⊆ V1; (ii) For all v ∈ V1∩V (G), the restriction f |Hv of f to Hv is a perfect Roman dominating function on Hv; (iii) For all v ∈ V2 ∩ V (G) for which V0 ∩ V (Hv) 6= ∅, V0 ∩NHv(V2 ∩ V (Hv)) = ∅. Proof : Assume that f ∈ PRD(G ◦ H). Let v ∈ V0 ∩ V (G). Then there exists a unique u ∈ V2 for which u ∈ NG◦H(v) = V (Hv)∪NG(v). If V2∩NG(v) = ∅, then V2∩V (Hv) = {u} and V0 ∩ V (Hv) ⊆ NHv(u). Suppose that V2 ∩ NG(v) 6= ∅. Then |V2 ∩ NG(v)| = 1 and V2 ∩V (Hv) = ∅. Moreover, if w ∈ V0 ∩V (Hv), then there exists a unique z ∈ V2 ∩V (Hv) such that wz ∈ E(Hv). Since vz ∈ E(G ◦H), this is impossible. Thus, V (Hv) ⊆ V1. This proves (i). Next, let v ∈ V1 ∩ V (G), and let w ∈ V0 ∩ V (Hv). Since f is a perfect Roman dominating function, there exists unique u ∈ V2 for which uw ∈ E(G ◦H). Since v ∈ V1, u ∈ V2 ∩V (Hv) and uw ∈ E(Hv). Thus, f |Hv is a perfect Roman dominating function on Hv, and (ii) holds. Statement (iii) is clear. Conversely, suppose that conditions (i), (ii) and (iii) hold for f , and let w ∈ V0. Then w ∈ V (Hv+v) for some v ∈ V (G). If w = v, then by condition (i), V2∩(V (Hv) ∪NG(w)) = {u} for some u ∈ V (G ◦ H). This means that V2 ∩ NG◦H(w) = {u}. Suppose that w ∈ V (Hv). We consider three cases: Case 1: Suppose that v ∈ V0. Since w ∈ V0 ∩ V (Hv), V (Hv) * V1. Thus, by condition (i) there exists u ∈ V (Hv) for which V2 ∩ V (Hv) = {u} and V0 ∩ V (Hv) ⊆ NHv(u). This means that V2 ∩NG◦H(w) = {u}. Case 2: Suppose that v ∈ V1. By condition (ii), there exists a unique u ∈ V2 ∩ V (Hv) such that uw ∈ E(Hv) ⊆ E(G ◦H). This implies that V2 ∩NG◦H(w) = {u}. Case 3: Suppose that v ∈ V2. Since w ∈ V0 ∩ V (Hv), condition (iii) implies that w /∈ NHv(V2 ∩ V (Hv). Thus, V2 ∩NG◦H(w) = {v}. Therefore, f is a perfect Roman dominating function on V (G ◦H). � Corollary 2.11. Let G and H be nontrivial graphs with G connected of order n. Then γPR(G ◦H) = 2n. Proof : By Theorem 2.7, the function f = (V0, V1, V2) defined by f(x) = 2 for all v ∈ V (G), and f(x) = 0 else, is a perfect Roman dominating function onG◦H. Thus, γPR(G◦H) ≤ 2n. Now, let f = (V0, V1, V2) be a γPR -function on V (G ◦ H). Let v ∈ V (G). Clearly, if v ∈ V2, then ∑ x∈V (Hv+v) f(x) ≥ 2. If v ∈ V0, then by Proposition 2.10(i) and since L. Paleta, F. Jamil / Eur. J. Pure Appl. Math, 13 (3) (2020), 529-548 538 |V (Hv| ≥ 2, ∑ x∈V (Hv+v) f(x) ≥ 2. Finally, if v ∈ V1, then by Proposition 2.10(ii),∑ x∈V (Hv+v) f(x) > 2. Therefore, γPR(G ◦H) = ωG◦H(f) = ∑ v∈V (G)  ∑ x∈V (Hv+v) f(x)  ≥ 2n. � 2.3. On the complementary prisms Let f = (V0, V1, V2) ∈ PRD(GG). Suppose that for the restriction f |G /∈ PRD(G). Then there exists v ∈ V (G) such that v ∈ V0 and V2 ∩NGG(v) = {v}. Let u ∈ V0 ∩ V (G). There exists w ∈ V (GG) such that V2 ∩ NGG(u) = {w}. If w = u, then uv /∈ E(G, and consequently, uv ∈ E(G), a contradiction. Thus, w ∈ V2∩V (G). This proves the following lemma. Lemma 2.12. Let G be any graph. If f ∈ PRD(GG), then f |G ∈ PRD(G) or f |G ∈ PRD(G). Proposition 2.13. Let G be a graph of order n. Then (i) γ(GG) < γPR(GG); (ii) γPR(GG) = 2 if and only if n = 1; (iii) γPR(GG) = 3 if and only if G ∈ {K2,K2}; (iv) If γ(G) = 1, then γPR(GG) ≤ n + 1 and equality is attained if degG(v) ≤ 3 for all v /∈ Dom(G) or G is the disjoint union of Kj ∈ {K1,K2}. Proof : Since GG is connected, (i) follows from Corollary 2.6. If n = 1, then GG = K2 and γPR(GG) = 2. Suppose that γPR(GG) = 2, and let f be a γPR -function of GG. By Lemma 2.12, we may assume that f |G ∈ PRD(G). If ωG(f |G) = 1, then n = 1. If ωG(f |G) = 2, then G = {v} with f(v) = f |G(v) = 2 and f(v) = 0. If G ∈ {K2,K2}, then GG is isomorphic to P4. Thus, γPR(GG) = 3. Conversely, suppose that γPR(GG) = 3. By Proposition 2.3(iii), ∆(GG) = 2n− 2. Let v ∈ V (GG) be such that degGG(v) = 2n − 2. Without loss of generality, assume that v ∈ V (G). Since NGG(v) ∩ V (G) = {v}, degG(v) = 2n− 3 ≤ n− 1. Necessarily, n ≤ 2. By (ii), n = 2 and G = K2. If γ(G) = 1, then by Proposition 2.2, γPR(GG) ≤ n+1. First, suppose that degG(v) ≤ 3 for all v /∈ Dom(G). Let f = (V0, V1, V2) be a γPR -function of GG. Since ωGG(f) ≤ n+ 1, V2 6= ∅. We consider two cases: L. Paleta, F. Jamil / Eur. J. Pure Appl. Math, 13 (3) (2020), 529-548 539 Case 1: Suppose that V2 ∩ V (G) = ∅. If V (G) ⊆ V1, then V (G) * V0 so that ωGG(f) ≥ n+ 1. Suppose that V (G) ∩ V0 6= ∅. Then ωGG(f) = ∑ w∈V0∩V (G) f(w) + ∑ w∈V1∩V (G) (f(w) + f(w)) ≥ n+ 1. Case 2: Assume that V2 ∩ V (G) 6= ∅. We consider two subcases: Subcase 2.1: Suppose that V2 contains a dominating vertex v of G. Since f is a γPR -function, NG(v) ∪ {v} ⊆ V0. Let w ∈ V (G) \ {v}. Suppose that w ∈ V0. There exists u ∈ V (G) such that NG(w) ∩ V2 = {u}. Since wv /∈ E(G), u 6= v. Thus, u ∈ V0 and v, u ∈ NGG(u) ∩ V2, a contradiction. This means that f(w) ≥ 1. Therefore, ωGG(f) = 2 + ∑ w∈V (G)\{v} f(w) ≥ 2 + n− 1 = n+ 1. Subcase 2.2: Suppose that V2 ∩Dom(G) = ∅. Choos v ∈ Dom(G). Put A = {w ∈ V (G) : f(w) = f(w) = 0}. If A = ∅, then f(w) + f(w) ≥ 1 for all w ∈ V (G) and since V2 ∩ V (G) 6= ∅, we have ωGG(f) ≥ n + 1. Suppose that A 6= ∅. Here, we work on two subcases: Subcase 2.2.1: Suppose that v ∈ V0. If f(v) = 2, then V (G) ∩ V2 = ∅ and so f(u) = 2 for each u ∈ V0 ∩ V (G). This implies that ωGG(f) ≥ n + 1. Suppose that f(v) = 1. Then there exists u ∈ V (G) such that V2 ∩ V (G) = {u}. Moreover, for each w ∈ A, wu ∈ E(G). Since degG(u) ≤ 3 and uv ∈ E(G), |A| ≤ 2. Suppose that A = {w}. There exists a ∈ V (G) such that u 6= a and NG(w) ∩ V2 = {a}. Since α = (f(u) + f(u)) + (f(w) + f(w)) + (f(a) + f(a)) ≥ 4, ωGG(f) = α+ ∑ x∈V (G)\{u,w,a} (f(x) + f(x)) ≥ 4 + (n− 4) + 1 = n+ 1. Now, suppose that A = {w, z}. There exist a, b ∈ V (G) such that a, b ∈ V2, wa, zb ∈ E(G) and a, b ∈ NG(u). Thus, f(u) = f(a) = f(b) = 1 and whether a = b or a 6= b, α = (f(u) + f(u)) + (f(w) + f(w)) + (f(z) + f(z)) + (f(a) + f(a)) + ( f(b) + f(b) ) ≥ 6. Thus, ωGG(f) = α+ ∑ x∈V (G)\{u,w,z,a,b} (f(x) + f(x)) ≥ 6 + (n− 6) + 1 = n+ 1. Subcase 2.2.2: Suppose that v, v ∈ V1. For each w ∈ A, there exist distinct vertices u, z ∈ V (G) such that u, z ∈ V2, uw ∈ E(G) and wz ∈ E(G). Again, for each u ∈ V2 ∩ V (G), since degG(u) ≤ 3, there can only be at most two vertices a, b ∈ A for which ua, ub ∈ E(G). Using similar arguments, if |A| ≤ 2, then ωGG(f) ≥ n + 1. To proceed, we only have to consider the case where 3 ≤ |A| ≤ 4. Other cases follow inductively. L. Paleta, F. Jamil / Eur. J. Pure Appl. Math, 13 (3) (2020), 529-548 540 Suppose that A = {x, y, w}. The only nontrivial scenario is the following: There exist a, c ∈ V2 ∩ V (G) and b ∈ V (G) such that b ∈ V2, ac /∈ E(G), wc ∈ E(G), {x, y} ⊆ NG(a), and {x, y, w} ⊆ NG(b). Since ab ∈ E(G), f(a) = 1. Thus, ωGG(f) = ∑ u∈{a,x,y,b,w,c} (f(u) + f(u)) + ∑ u∈V (G)\{a,b,c,x,y,w} (f(u) + f(u)) ≥ 7 + (n− 7) + 2 > n+ 1. Finally, suppose that A = {x, y, z, w}. It is enough to consider only the following nontrivial case: There exist a, c ∈ V2 ∩ V (G) and b ∈ V (G) such that b ∈ V2, ac /∈ E(G), {x, y} ⊆ NG(a), {w, z} ⊆ NG(c), and {x, y, z, w} ⊆ NG(b). Since ab, cb ∈ E(G), f(a) = f(c) = 1. Hence, ωGG(f) = ∑ u∈{a,b,c,x,y,w,z} (f(u) + f(u)) + ∑ u∈V (G)\{a,b,c,x,y,w,z} (f(u) + f(u)) ≥ 8 + (n− 8) + 2 > n+ 1. All of the above cases show that γPR(G) = ωGG(f) ≥ n+ 1. Next, suppose that G is the union of Kj ∈ {K1,K2}, and let f = (V0, V1, V2) be a γPR -function of GG. As shown previously, we may assume that V2 ∩ V (G) 6= ∅, and if V2 contains a dominating vertex of G, then ωGG(f) ≥ n + 1. Henceforth, we assume that V2∩Dom(G) = ∅. Pick v ∈ Dom(G). Then v ∈ Iso(G). Note that for all x ∈ Iso(G), x /∈ A = {w ∈ V (G) : f(w) = f(w) = 0} so that (f(x) + f(x)) ≥ 1. Also, for all x, y ∈ V (G) for which xy ∈ E(G), if x ∈ A, then y ∈ V2 and so (f(x) + f(x)) + (f(y) + f(y)) ≥ 2. Thus, if v ∈ V0 and u ∈ V (G) such that V2 ∩ V (G) = {u}, then ωGG(f) = (f(u) + f(u)) + ∑ x∈Iso(G) (f(x) + f(x)) + ∑ xy∈E(G) ((f(x) + f(x)) + (f(y) + f(y))) ≥ n+ 1. On the other hand, if v ∈ V1, then f(v) = 1 and ωGG(f) = (f(v) + f(v)) + ∑ x∈Iso(G)\{v} (f(x) + f(x)) + ∑ xy∈E(G) ((f(x) + f(x)) + (f(y) + f(y))) ≥ n+ 1. Therefore, γPR(GG) ≥ n+ 1. � L. Paleta, F. Jamil / Eur. J. Pure Appl. Math, 13 (3) (2020), 529-548 541 As shown by the graph G in Figure 1, strict inequality may be attained in Proposition 2.13(iv) if we remove the condition that degG(v) ≤ 3 for all nondominating vertices v of G. For such G, γPR(GG) = 6 < |V (G)|+ 1. .................................... .................................... .................................... .................................... .................................... .................................... .......... ......... ......... ......... ......... ......... ......... ......... ... .......... ......... ......... ......... ......... ......... ......... ......... ... ........................................................................................................................................................ ............................................................................................................................................................................... ............................................................................................................................................................................ ......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... ..... .................................................................................................. ............................................................................................................................................................................................................................................................................................................................................ G : .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .......... ......... ......... ......... ......... ......... ......... ......... ... .......... ......... ......... ......... ......... ......... ......... ......... ... ........................................................................................................................................................ ............................................................................................................................................................................... ............................................................................................................................................................................ ......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... ..... .................................................................................................. ............................................................................................................................................................................................................................................................................................................................................ ........................................................................ ......... ........ ........ ........ ........ ........ ........ ........ ................ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ .. ......... ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ....... ......... ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ .. ......... ........ ........ ........ ........ ........ ........ ........ ....... ............................................................................................................................................................... ..................................................................................................................................................................................................................................... ............................................................................... .............................................................................. .............................................................................. ............................. ............... .............. .............. .............. .............. .............. ... ............................................................. ................ ............... ............... ............... ............... ............... ............... .............. .......... ......... ......... ......... ......... ......... ......... ......... .. 0 00 0 0 0 0 0 2 2 1 1 GG Figure 1: Graph G with γ(G) = 1 and γP R (GG) < |V (G)|+ 1 Pick G = Kn. By Proposition 2.13(iv) and Corollary 2.5, γPR(GG) = 1 + max{γPR(G), γPR(G)}. Observe also that if v ∈ V (G), then f = (V (G) \ {v},∅, {v}) ∈ PRD(G) and γPR(GG) = ωG(f) + n − |V2|. The following result shows that these two expressions serve as sharp lower and upper bounds, respectively, of γPR(GG) for a general graph G. Theorem 2.14. For any graph G, 1 + max{γPR(G), γPR(G)} ≤ γPR(GG) ≤ ρ, where ρ = min{ωG(f) + n− |V2| : f = (V0, V1, V2) ∈ PRD(G) ∪ PRD(G)}. Proof : WLOG assume that for some f = (V0, V1, V2) on G, ρ = ωG(f) + n− |V2|. Extend f to GG by defining f(v) = 0 for all v ∈ V2 and f(v) = 1 for all v ∈ V (G) \ V2. Then the extension f ∈ PRD(GG) and γPR(GG) ≤ ωG(f) + n− |V2|. Thus, γPR(GG) ≤ ρ. In view of Proposition 2.13(iv), we assume that neither G nor G is a complete graph. WLOG, assume that γPR(G) ≥ γPR(G). Let f = (V0, V1, V2) be a γPR -function on GG. If V (G) ⊆ V0, then V2 = V (G) so that γPR(GG) = 2|V2| = |V (GG)|. Since GG is connected, n = 1 by Corollary 2.5 and Corollary 2.3(ii). This is contradictory to our assumption. Thus, V (G) ∩ (V1 ∪ V2) 6= ∅. If V2 ∩ V (G) = ∅, then g = (V0 ∩ V (G), V1 ∩ V (G), V2) ∈ PRD(G). Since V (G) ∩ V1 6= ∅, γPR(GG) = ωGG(f) ≥ ωG(g) + 1 ≥ γPR(G) + 1. Suppose that V2 ∩ V (G) 6= ∅, and let A = {v ∈ V0 : V2 ∩ NGG(v) = {v}}. Define g = (V ∗0 , V ∗ 1 , V ∗ 2 ) on G by g(x) = { f(x), if x ∈ V (G) \A; 1, if x ∈ A. L. Paleta, F. Jamil / Eur. J. Pure Appl. Math, 13 (3) (2020), 529-548 542 Then g ∈ PRD(G) with V ∗0 = (V0 \A)∩V (G), V ∗1 = A∪(V1 ∩ V (G)) and V ∗2 = V2∩V (G). Since {v : v ∈ A} ⊆ V2 ∩ V (G), γPR(GG) = ωG(g) + ∑ x∈V (G) f(x)− |A| ≥ ωG(g) + 1 ≥ γPR(G) + 1. � If G = C5, then G and G are isomorphic and GG is isomorphic to the Petersen graph. Observe that γPR(GG) = 7, γPR(G) = γPR(G) = 4 and ρ = 8 so that 1 + max{γPR(G), γPR(G)} < γPR(GG) < ρ. This shows that strict inequality can be attained at each side of the inequalities in Theorem 2.14. 2.4. On the edge corona of graphs Given graphs G and H, we write Huv to denote that copy of H that is being joined with the endvertices of the edge uv ∈ E(G) in the edge corona G �H. If H = {x}, then we write V (Huv) = {xuv}. For an f ∈ PRD(G), we write for each a, b ∈ {0, 1, 2}, Eab(f ;G) = {uv ∈ E(G) : (f(u) = a ∧ f(v) = b) ∨ (f(u) = b ∧ f(v) = a)}, where “∧“ and “∨“ denote “and“ and “or“, respectively. Theorem 2.15. Let G be a nontrivial connected graph and H any graph of order n. Then γPR(G �H) ≤ α, where α = min g∈PRD(G) ( ωG(g) + |E11(g;G)|γPR(H) + n (|E01(g;G)|+ |E22(g;G)|+ E00(g;G)|) ) , and this upper bound is sharp. Proof : Let g ∈ PRD(G). If no confusion arises, we write Eab = Eab(g;G). Let h ∈ PRD(H). For each ab ∈ E(G), we define a copy hab of h on Hab. Define the function f = (V0, V1, V2) on G �H by f(x) =  g(x), if x ∈ V (G); huv(x), if x ∈ V (Huv), where uv ∈ E11; 0, if x ∈ V (Huv), where uv ∈ E02 ∪ E12; 1, if x ∈ V (Huv),where uv ∈ E01 ∪ E00 ∪ E22. L. Paleta, F. Jamil / Eur. J. Pure Appl. Math, 13 (3) (2020), 529-548 543 We claim that f ∈ PRD(G �H). First, note that f |G = g = (V0 ∩ V (G), V1 ∩ V (G), V2 ∩ V (G)). Let x ∈ V0. Suppose that x ∈ V (G). ThenNG�H(x) = NG(x)∪ ( ∪u∈NG(x)V (Hux) ) . Since g ∈ PRD(G), |V2 ∩ NG(x)| = 1, say V2 ∩ NG(x) = {z}. Let u ∈ NG(x), and let y ∈ V (Hxu). If u ∈ V0 ∪ V1, then y ∈ V1. On the other hand, if u ∈ V2, then y ∈ V0. Thus, V2 ∩ V (Hux) = ∅. Since u is arbitrary, V2 ∩ ( ∪u∈NG(x)V (Hux) ) = ∅ and so V2 ∩ NG�H(x) = {z}. Suppose that x ∈ V (Huv) for some uv ∈ E(G). Then NG�H(x) = {u, v} ∪ NHuv(x). Since f(x) = 0, uv /∈ E00 ∪ E22 ∪ E01. If uv ∈ E11, then huv(x) = 0 and there exists exactly one y ∈ V (Huv) such that xy ∈ E(Huv) and f(y) = huv(y) = 2. In this case, V2 ∩ NG�H(x) = V2 ∩ NHuv(x) = {y}. Suppose that uv ∈ E02 ∪ E12. Since V (Huv) ⊆ V0, either V2 ∩NG�H(x) = {u} or V2 ∩NG�H(x) = {v}. Accordingly, f ∈ PRD(G �H). Therefore, γPR(G �H) ≤ ωG(g) + |E11|ωH(h) + ∑ x∈{V (Huv):uv∈E00∪E01∪E22} f(x) = ωG(g) + |E11|ωH(h) + n (|E01|+ |E22|+ E00|) . Since h is arbitrary, the desired inequality holds. Consider the graph G � P3 in Figure 2, where G is the caterpillar ca(2, 0, 2) with the corresponding vertex labelling. The function g on V (G) given by g(x) = g(z) = 2, g(y) = 1 and g(x) = 0 else is in PRD(G). Since E00 = E01 = E22 = E00 = ∅, α ≤ ωG(g) = 5 so that γPR(G �P3) ≤ 5. Now, note that {x, z} is the unique γ-set of G �P3. However, {x, z} ....................................................................................................................................... ....................................................................................................................................... .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ .. . ................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ .. . ................................... .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ .. . ................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ .. . ................................... .................................... G x y z ....................................................................................................................................... ....................................................................................................................................... .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ .. . ................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ .. . ................................... .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ .. . ................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ .. . ................................... .................................... ......... ........ .................................... ......... ........ .................................... .................................... ......... ........ .................................... ......... ........ .................................... .................................... ......... ........ .................................... ......... ........ .................................... .................................... ......... ........ .................................... ......... ........ .................................... .................................... ..................................................... ..................................................... .................................... ................. ..................................................... ........................................................................ G � P3 x y z .............................................................................................................................. ............................................................................................................... ...................................................................................................... ................................. ................................ ................................ ..... ................... .................. .................. .................. .................. .................. .. .............. ............. ............. ............. ............. ............. ............. ............. ............. ........ ............... .............. .............. .............. .............. .............. .............. .............. .............. ........ .................... ................... ................... ................... ................... ................... ...... .................................... ................................... ................................... ....... ................................................................................................................. ......................................................................................................................... ....................................................................................................................................... .............. ............. ............. ............. ............. ............. ............. ............. ............. ........ ................... .................. .................. .................. .................. .................. .. ................................. ................................ ................................ ..... ...................................................................................................... ............................................................................................................... .............................................................................................................................. .............................................................................................................................. ............................................................................................................... ...................................................................................................... ................................. ................................ ................................ ..... ................... .................. .................. .................. .................. .................. .. .............. ............. ............. ............. ............. ............. ............. ............. ............. ........ ........................................................................................ ................................................................... ............................................................. ......... ......... ......... ......... ..... ............ ........... ........... ........... ........... ........... ............... .............. .............. .............. .............. .............. ... .......... ......... ......... ......... ......... ..... ............ ........... ........... ........... ........... ........... ............... .............. .............. .............. .............. .............. ........................................................................................... ................................................................... ................................................... .......... ......... ......... ......... ......... ..... ............ ........... ........... ........... ........... ........... ............... .............. .............. .............. .............. .............. ... Figure 2: The edge corona G � P3 with γP R (G � P3) = 5 does not form the V1 ∪ V2 for any f = (V0, V1, V2) ∈ PRD(G �P3). Thus, γPR(G �P3) ≥ 5. � The value of α in Theorem 2.15 is not necessarily determined by a γPR -function on G. Consider the two copies of the edge corona P5�C4 given in Figure 3 with the corresponding assignment of colours to the vertices. Here, we write P5 = {x1, x2, x3, x4, x5}. Observe that f = ({x1, x3, x4},∅, {x2, x5}) is a γPR -function on P5 (see right-hand side figure), while g = ({x1, x5}, {x3}, {x2, x4}) ∈ PRD(P5) but not a γPR -function on P5 (see left-hand side figure). Verify that γPR(P5 � C4) = 5 and is determined by the function g. From Theorem 2.15 and as illustrated in the preceding example, the value of α in Theorem 2.15 is determined by the functions g ∈ PRD(G) for which most of the sets L. Paleta, F. Jamil / Eur. J. Pure Appl. Math, 13 (3) (2020), 529-548 544 ....................................................................................................................................... ....................................................................................................................................... ....................................................................................................................................... ....................................................................................................................................... .................................... ............ ........... ..... .................................... ................................................................................ .............. ............. ..... . ................................... ....................................... ........................................................................ ............ ........... ..... .................................... ................................................................................ .............. ............. ..... . ................................... ....................................... ........................................................................ ............ ........... ..... .................................... ................................................................................ .............. ............. ..... . ................................... ....................................... ........................................................................ ............ ........... ..... .................................... ................................................................................ .............. ............. ..... . ................................... ....................................... ........................................................................ ......... ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ..... .......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ........... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... ... ........... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... ................................................................................................................................ ................................................................................................................................................. ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ..... ................................................................................................................ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ..... .......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ........... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... ... ........... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... ................................................................................................................................ ................................................................................................................................................. ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ..... ................................................................................................................ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ..... .......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ........... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... ... ........... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... ................................................................................................................................ ................................................................................................................................................. ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ..... ................................................................................................................ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ..... .......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ........... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... ... ........... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... ................................................................................................................................ ................................................................................................................................................. ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ..... ....................................................................................................... x1 x2 x3 x4 x5 2 20 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 1 ....................................................................................................................................... ....................................................................................................................................... ....................................................................................................................................... ....................................................................................................................................... .................................... ............ ........... ..... .................................... ................................................................................ .............. ............. ..... . ................................... ....................................... ........................................................................ ............ ........... ..... .................................... ................................................................................ .............. ............. ..... . ................................... ....................................... ........................................................................ ............ ........... ..... .................................... ................................................................................ .............. ............. ..... . ................................... ....................................... ........................................................................ ............ ........... ..... .................................... ................................................................................ .............. ............. ..... . ................................... ....................................... ........................................................................ ......... ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ..... .......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ........... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... ... ........... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... ................................................................................................................................ ................................................................................................................................................. ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ..... ................................................................................................................ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ..... .......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ........... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... ... ........... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... ................................................................................................................................ ................................................................................................................................................. ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ..... ................................................................................................................ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ..... .......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ........... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... ... ........... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... ................................................................................................................................ ................................................................................................................................................. ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ..... ................................................................................................................ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ..... .......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ........... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... ... ........... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... ................................................................................................................................ ................................................................................................................................................. ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ..... ....................................................................................................... x1 x2 x3 x4 x5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 2 1 1 1 1 Figure 3: The edge corona P5 � C4 E00(g;G), E22(g;G), E11(g;G) and E01(g;G) are empty. In view of such, the following observation can be easily verified. Corollary 2.16. Let H be any nontrivial graph of order m. then (i) For the path Pn on n ≥ 2 vertices, γPR(Pn �H) = 3bn−22 c+ 2. (ii) If m ≥ 3, then for the cycle Cn on n ≥ 3 vertices, γPR(Cn �H) = { 3k, if n = 2k; 3k + 1 + γPR(H), if n = 2k + 1. (iii) If m ≥ 3, then for 2 ≤ n ≤ k, γPR(Kn,k �H) = 2n+ k. Theorem 2.17. Let G be a nontrivial connected graph. Then γPR(G �K1) = min g∈PRD(G) (ωG(G) + |E00(g;G)|+ |E01(g;G)|+ |E11(g;G)|+ |E22(g;G)|) . Proof : Put α = min{ωG(G) + |E00(g;G)|+ |E01(g;G)|+ |E11(g;G)|+ |E22(g;G)| : g ∈ PRD(G)}. By Theorem 2.15, γPR(G �K1) ≤ α. Let f = (V0, V1, V2) be a γPR -function on G �K1. Suppose that the restriction f |G of f to G is not a perfect Roman dominating function on G. We will construct a γPR -function g on G �K1 such that ωG�K1(g) = ωG�K1(f) and its restriction g|G to G is a perfect Roman dominating function on G. There exists u ∈ V0 ∩ V (G) such that uv /∈ E(G) for all v ∈ V2∩V (G). This means that there exists v ∈ NG(u) such that V2∩NG�K1(u) = {xuv}. Case 1: Suppose that v /∈ V0. Define f1 = (V 1 0 , V 1 1 , V 1 2 ) on G�K1 by f1(u) = f1(xuv) = 1 and f1(x) = f(x) for all x ∈ V (G � K1) \ {u, xuv}. Then f1 ∈ PRD(G � K1) with ωG�K1(f1) = ωG�K1(f). Case 2: Suppose that v ∈ V0. If (NG(v) \ {u})∩ V0 = ∅, then take f1 = (V 1 0 , V 1 1 , V 1 2 ) on G given by f1(v) = 2, f1(xuv) = 0 and f1(x) = f(x) for all x ∈ V (G�K1)\{v, xuv}. Then f1 ∈ PRD(G�K1) and ωG�K1(f1) = ωG�K1(f). Suppose that B = (NG(v) \ {u})∩V0 6= ∅. L. Paleta, F. Jamil / Eur. J. Pure Appl. Math, 13 (3) (2020), 529-548 545 Necessarily, xvw ∈ V1 for each w ∈ B. In this case, take the function f1 = (V 1 0 , V 1 1 , V 1 2 ) on G �K1 given by f1(x) =  2, if x = v; 0, if x ∈ {xuv, xvw : w ∈ B}; 1, if x ∈ B; f(x), if x ∈ V (G �K1) \ (B ∪ {xvw : w ∈ B}) . Then f1 ∈ PRD(G � K1) with V 1 0 = (V0 \ {v}) ∪ {xuv, xvw : w ∈ B}, V 1 1 = (V1 \ {xvw : w ∈ B}) ∪ B and V 1 2 = (V2 \ {xuv}) ∪ {v}. It is easy to verify that f1 ∈ PRD(G �K1) and ωG�K1(f1) = ωG�K1(f). If f1|G /∈ PRD(G), then we follow the same process and obtain f2 ∈ PRD(G�K1) with ωG�K1(f2) = ωG�K1(f1) = ωG�K1(f). If necessary, we do a finitely many repetitions of the process until we obtain a function g = fk ∈ PRD(G�K1) for which ωG�K1(g) = ωG�K1(f) and g|G ∈ PRD(G). By the definition of α, γPR(G �K1) = ωG�K1(g) ≥ α. � The value of γPR(G �K1) in Theorem 2.17 is determined by the functions g ∈ PRD(G) for which the sets E22 and E11 are empty. With this observation, it can readily be verified that for n ≥ 1 and m ≥ 3, γPR(Pn �K1) = bn− 1 3 c+ γPR(Pn) and γPR(Cm �K1) = dn 3 e+ γPR(Cm). 2.5. On the composition of graphs Given S ⊆ V (G[H]), we write SG = {x ∈ V (G) : (x, y) ∈ S for some y ∈ V (H)}, which is called the projection of G on G[H]. Proposition 2.18. Let G and H be connected graphs, G noncomplete and H of order n with γ(H) = 1. Then γPR(G[H]) ≤ α, where α = min{(n− 1) (|V1|+ |V2 ∩NG(V2)|) + ωG(f) : f = (V0, V1, V2) ∈ PRD(G)}. Proof : Let v ∈ V (H) for which NH [v] = V (H). Let f = (V0, V1, V2) ∈ PRD(G) such that V2 6= ∅. Define g = (V ∗0 , V ∗ 1 , V ∗ 2 ) on G[H] by g((x, y)) =  0, if (x ∈ V2 \NG(V2) ∧ y 6= v) ∨ (x ∈ V0) ; 1, if (x ∈ V2 ∩NG(V2) ∧ y 6= v) ∨ (x ∈ V1) ; 2, if x ∈ V2 and y = v. with V ∗0 = ((V2 \NG(V2))× (V (H) \ {v})) ∪ (V0 × V (H)), V ∗2 = V2 × {v} and V ∗1 = (V1 ∪ V (H)) ∪ ((V2 ∩NG(V2))× (V (H) \ {v})). Let (x, y) ∈ V ∗0 . If x ∈ V2, then x /∈ NG(V2) so that NG[H]((x, y)) ∩ V ∗2 = {(x, v)}. If x ∈ V0, then there exists u ∈ V2 such that NG(x) ∩ V2 = {u}, which implies that NG[H]((x, y)) ∩ V ∗2 = {(u, v)}. Thus, g ∈ PRD(G[H]). Therefore, γPR(G[H]) ≤ |V ∗1 |+2|V ∗2 | = (n−1) (|V1|+ |V2 ∩NG(V2)|)+ωG(f). Since f is arbitrary, the desired inequality is established. � L. Paleta, F. Jamil / Eur. J. Pure Appl. Math, 13 (3) (2020), 529-548 546 Proposition 2.19. Let G be a nontrivial connected graph and p ≥ 2. Then γPR(G[Kp]) = α, where α = min{(n− 1) (|V1|+ |V2 ∩NG(V2)|) + ωG(f) : f = (V0, V1, V2) ∈ PRD(G)}. Proof : Let f = (V0, V1, V2) be a γRP -function on V (G[H]). Then V2 6= ∅ and V0 6= ∅. First, we claim that (V0)G ∩ (V1)G = ∅. Suppose not, and let (x, y) ∈ V1 be such that (x, z) ∈ V0 for some z 6= y. There exists unique (u, v) ∈ V2 for which (x, z)(u, v) ∈ E(G[Kp]. If u = x, then since y 6= v, (x, y)(u, v) ∈ E(G[Kp]). Thus, whether u = x or x 6= u, (x, y)(u, v) ∈ E(G[Kp]). By Proposition 2.1, there exists (a, b) ∈ V2 \ {(u, v)} such that (x, y)(a, b) ∈ E(G[Kp]). Using the same argument, whether x = a or x 6= b, (x, z)(a, b) ∈ E(G[Kp]). This is a contradiction since (x, z) ∈ V0. Fix v ∈ V (Kp). Define A = {(x, v) : x ∈ (V0)G ∩ (V2)G}, B = {(x, y) ∈ V2 : x /∈ (V0)G} and C = {(x, y) ∈ V2 : x ∈ (V0)G , y 6= v}. Put V ∗0 = (V0 \A) ∪ C, V ∗1 = V1, and V ∗2 = A ∪B. Then {V ∗0 , V ∗1 , V ∗2 } forms a partition of V (G[Kp]). Note here that, in particular, since (V0)G ∩ (V1)G = ∅ and V1 ∩ V2 = ∅. Now, let (x, y) ∈ V ∗0 . Case 1: Suppose that (x, y) ∈ V0 \A. There exists (u,w) ∈ V2 such that NG[Kp]((x, y))∩ V2 = {(u,w)}. If u /∈ (V0)G, then (u,w) ∈ B and NG[Kp]((x, y)) ∩ V ∗2 = {(u,w)}. On the other hand, if u ∈ (V0)G, then (u, v) ∈ A and NG[Kp]((x, y)) ∩ V ∗2 = {(u, v)}. Case 2: Suppose that (x, y) ∈ C and let z ∈ V (Kp) \ {y} for which (x, z) ∈ V0. Since (x, y)(x, z) ∈ E(G[Kp]) and (x, y) ∈ V2, NG[Kp]((x, z)) ∩ V2 = {(x, y)}. This means that (x,w) /∈ V2 for all w ∈ V (Kp)\{y} and (u,w) /∈ V2 for all u ∈ NG(x) and for all w ∈ V (Kp). Thus, NG[Kp]((x, y)) ∩ V ∗2 = NG[Kp]((x, y)) ∩A = {(x, v)}. Accordingly, the function g = (V ∗0 , V ∗ 1 , V ∗ 2 ) ∈ PRD(G[Kp]). Since V ∗1 = V1 and |V ∗2 | ≤ |V2|, ωG[Kp](f) ≥ ωG[Kp](g). Because f is a γPR -function of G[Kp], ωG[Kp](f) = ωG[Kp](g) and g is a γPR -function of G[Kp]. Define the function h = (V h 0 , V h 1 , V h 2 ) on G by h(x) =  2, if x ∈ (V ∗2 )G ; 1, if x ∈ (V ∗1 )G \ (V ∗2 )G ; 0, else. Let x ∈ V h 0 . Then (x, y) ∈ V ∗0 for all y ∈ V (Kp). Pick y ∈ V (Kp). There exists a unique (u, v) ∈ V ∗2 for which (x, y)(u, v) ∈ E(G[Kp]). It follows that u ∈ V h 2 and ux ∈ E(G). Moreover, u is unique in this sense as (u, v) is for (x, y). Thus, h ∈ PRD(G). Finally, let x, u ∈ V h 2 for which xu ∈ E(G). Let y, v ∈ V (Kp) such that (x, y), (u, v) ∈ V ∗2 . Since g is a γPR -function of G[Kp], (x, a), (u, b) ∈ V ∗1 for all a ∈ V (Kp)\{y} and for all REFERENCES 547 b ∈ V (Kp) \ {v}. On the other hand, by the definition of h, for each x ∈ V h 1 , (x, y) ∈ V ∗1 for all y ∈ V (Kp). Thus, |V ∗1 | ≥ p|V h 1 |+ (p− 1)|V h 2 ∩NG(V h 2 )|. Therefore, γPR(G[Kp]) = ωG[Kp](g) = |V ∗1 |+ 2|V ∗2 | ≥ p|V h 1 |+ (p− 1)|V h 2 ∩NG(V h 2 )|+ 2|V h 2 | = (p− 1) ( |V h 1 |+ |V h 2 ∩NG(V h 2 )| ) + ωG(h) ≥ α. The desired equality is completed by Proposition 2.18 � Equality in Proposition 2.18 is possible even if H is not complete. Consider the graph G[P3] in Figure 4, with G being the caterpillar graph ca(0, 2, 0, 2, 0). Observe that α = 7. ....................................................................................................................................... ....................................................................................................................................... .................................... ................................................... .................................... ........................................................................................................................................................................... .................................... .......................... ......................... ......................... .................................... .................................... ................... .................. .............. .................................... ....................................................................................................................................... .................................................................................................................................................... .................................... .................................... G .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... ....................................................................................................................................... ....................................................................................................................................... ....................................................................................................................................... ....................................................................................................................................... ....................................................................................................................................... ....................................................................................................................................... ....................................................................................................................................... ....................................................................................................................................... ....................................................................................................................................... ......... ........ ........ ........ ........ ........ ........ ........ ....... .................................... ......... ........ ........ ........ ........ ........ ........ ........ ....... .................................... .................................... ......... ........ ........ ........ ........ ........ ........ ........ ....... .................................... ......... ........ ........ ........ ........ ........ ........ ........ ....... .................................... .................................... ......... ........ ........ ........ ........ ........ ........ ........ ....... .................................... ......... ........ ........ ........ ........ ........ ........ ........ ....... .................................... .................................... ................................................................................................................................................................................................................................. ........................................................................................................................................................................................... .............. ............. ............. ............. ............. ............. ............. ............. ............. ........ ............................................................................................................................................................................................................................................ .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... ...... .............. ............. ............. ............. ............. ............. ............. ............. ............. ........ ................................................................................................... ................................................................................................... .............. ............. ............. ............. ............. ............. ............. ............. ............. ........ ........... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... ....................................................................................................................................................................................................................................... .............. ............. ............. ............. ............. ............. ............. ............. ............. ........ ........................................................................................................................................................................................... ................................................................................................................................................................................................................................. ......... ........ ........ ........ ........ ........ ........ ........ ....... ......... ........ ........ ........ ........ ........ ........ ........ ....... ............................................................................................................... ............ ........... ........... ........... ........... ........... ............ ........... ........... ........... ........... ........... ............................................................................................................... ................................................... ................................................... ................................................... ............................................................................................................................................................................................ .......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ........ ........ ........ ........ ........ ........ ........ ....... ......... ........ ........ ........ ........ ........ ........ ........ ....... .............................................................................................................................. .............. ............. ............. ............. ............. ............. ............. ............. ............. ........ .............. ............. ............. ............. ............. ............. ............. ............. ............. ........ .............................................................................................................................. ................................................................................................... ................................................................................................... ................................................................................................... ...................................................................................................................................................................................................... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... ...... ......... ........ ........ ........ ........ ........ ........ ........ ....... ......... ........ ........ ........ ........ ........ ........ ........ ....... ............................. ............................ ............................ . ................................................................................................. ............................................................................................................................................................... ............ ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ............................. ............................ ............................ . .................................................................................................... .......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... .. ............ ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ................................... .................................. ................ ......... ........ ........ ........ ........ ........ ........ ........ ....... ......... ........ ........ ........ ........ ........ ........ ........ ....... .......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... .. ................................................................... ................................................................... .......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... .. ................... .................. .............. ................... .................. .............. ................... .................. .............. .......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ....... ........................................................................................................................................ ......... ........ ........ ........ ........ ........ ........ ........ ....... ......... ........ ........ ........ ........ ........ ........ ........ ....... .............. ............. ............. ............. ............. ............. ............. ............. ............. ........ .............................................................................................................................. .............................................................................................................................. .............. ............. ............. ............. ............. ............. ............. ............. ............. ........ ................................................................................................... ................................................................................................... .............................................................................................................. .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... ................................................................................................................................................................................................. ......... ........ ........ ........ ........ ........ ........ ........ ....... ......... ........ ........ ........ ........ ........ ........ ........ ....... ...................................................................................... ................. ................ ................ ................ ................ ................ ........... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... ........ ..................................................................................................................................... ...................................................................................... ................ ............... ............... ............... ............... ............... ......... ......................................................................................................................................................................................................... ..................................................................................................................................... ..................................................................................... • • • • • G[P3] Figure 4: Graph G with γP R (G[P3]) = 7 On the other hand, γPR(G[P3]) = 7, which is determined by (V0, V1, V2) ∈ PRD(G[P3]), where V1 and V2 are the sets of all red and all black vertices, respectively, in G[P3] and V0 = V (G[P3]) \ (V1 ∪ V2). Acknowledgements This research is fully funded by the Commission on Higher Education (CHED) Philip- pines under the CHED K-12 Transition Program and University of Southern Mindanao Research and Faculty Development Program. References [1] H. Abdollhzadeh Ahangar. M. Chellali and S.M. Sheikholeslami, Outer independent double Roman domination. Appl. Math. Comput., 364(124617), 2020. [2] A. Alhashim. W. Desormeaux and T. Haynes. Roman domination in complementary prisms. Australian Journal of Combinatorics, 68(2):218–228, 2017. [3] J. Arquilla and H. Fredricksen. “Graphing“ an optimal grand strategy. Military Operations Research, 1:3–19, 1995. [4] C. Berge. The theory of Graphs and its Applications . Wiley, New York, 1962. REFERENCES 548 [5] F. Buckley and F. Harary. Distance in Graphs . Addison-Wesley, Redwood City, CA, 1990. [6] S. Canoy. R. Mollejon and J.G. Canoy. Hop dominating sets in graphs under binary operations. European Journal of Pure and Applied Mathematics, 12(4):1455–1463, 2019. [7] B. Chaluvaraju and V. Chaitra. Roman domination in complimentary prism. Inter- national J.Math. Combi., 2:24–31, 2012. [8] E. Cockayne. P. Dreyer Jr., S.M. Hedetniemi and S.T. Hedetniemi. Roman domina- tion in graphs. Discrete Mathematics, 278:11–22, 2004. [9] E. Cockayne and S. Hedetniemi. Towards a theory of domination in graphs. Networks, 7(3):1977, 1977. [10] P. Dankelmann, D. Day, D. Erwin, S. Mukwembi, and H. Swart. Domination with exponential decay. Discrete Mathematics, 309:5877–5883, 2009. [11] W. Desormeaux. T.W. Haynes and M.A. Henning. An extremal problem for to- tal domination stable graphs upon edge removal. Discrete Applied Mathematics, 159:1048–1052, 2011. [12] O. Favaron. , H. Karami and R. Khoeilar and S.M. Sheikholeslami. On the Roman domination number of a graph. Discrete Mathematics, 309:3447–3451, 2009. [13] T. Haynes, S.T. Hedetniemi, and P.J. Slater. Fundamentals of Domination in Graphs . Marcel Dekker, Inc., New York, 1998. [14] M. Henning. W. Klostermeyer and G. MacGillivray. Perfect Roman domination in trees. Discrete Applied Mathematics, 236:235–245, 2018. [15] M. Henning and W. Klostermeyer. Perfect Roman domination in regular grahs. Ap- plicable Analysis and Discrete Mathematics, 12(1):143–152, 2018. [16] Y. Kwon and J. Lee. Perfect dominating sets in Cayley graphs. Discrete Applied Mathematics, 162:259–263, 2014. [17] C.S. Revelle and K.E. Rosing. Defendens imperium romanum: a classical problem in military strategy. Amer. Math. Monthly, 107(7):585–594, 2000. [18] I. Stewart. Defend the Roman Empire. Sci. Amer., 281(6):136–139, 1999. [19] J. Yue and J. Song. Note on the perfect Roman domination number of graphs. Applied Mathematics and Computation, 364:1–5, 2020. [20] J. Yue, M. Wei, M. Li, and G. Liu. On the double roman domination of graphs. Applied Mathematics and Computation, 338:669–675, 2018.