EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS Vol. 16, No. 2, 2023, 847-863 ISSN 1307-5543 – ejpam.com Published by New York Business Global On Double Roman Dominating Functions in Graphs Jerry Boy G. Cariaga1,∗, Ferdinand P. Jamil1,2 1 Department of Mathematics and Statistics, College of Science and Mathematics, 2 Center for Graph Theory, Premier Research Institute of Science and Mathematics, MSU-Iligan Institute of Technology, 9200 Iligan City, Philippines Abstract. Let G be a connected graph. A function f : V (G) → {0, 1, 2, 3} is a double Roman dominating function of G if for each v ∈ V (G) with f(v) = 0, v has two adjacent vertices u and w for which f(u) = f(w) = 2 or v has an adjacent vertex u for which f(u) = 3, and for each v ∈ V (G) with f(v) = 1, v is adjacent to a vertex u for which either f(u) = 2 or f(u) = 3. The minimum weight ωG(f) = ∑ v∈V (G) f(v) of a double Roman dominating function f of G is the double Roman domination number of G. In this paper, we continue the study of double Roman domination introduced and studied by R.A. Beeler et al. in [2]. First, we characterize some double Roman domination numbers with small values in terms of the domination numbers and 2-domination numbers. Then we determine the double Roman domination numbers of the join, corona, complementary prism and lexicographic product of graphs. 2020 Mathematics Subject Classifications: 05C69 Key Words and Phrases: Domination number, 2-domination number, double Roman dominat- ing function, double 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 with V (G) and E(G) being the vertex set and edge set of G, respectively. For S ⊆ V (G), the symbol |S| refers to the cardinality of S. In particular, |V (G)| is the order of G. For other basic concepts not presented but are used here are adopted from ([4, 11]). For a vertex v of a graph G, the open neighborhood of v refers to the set NG(v) = {u ∈ V (G) : uv ∈ E(G)} while its closed neighborhood is the set NG[v] = {v} ∪NG(v). Vertex v is an isolated vertex if NG(v) = ∅. For S ⊆ V (G), the open neighborhood and closed neighborhood of S are the sets NG(S) = ∪v∈SNG(v) and NG[S] = ∪v∈SNG[u], respectively. ∗Corresponding author. DOI: https://doi.org/10.29020/nybg.ejpam.v16i2.4653 Email addresses: jerryboy.cariaga@g.msuiit.edu.ph (J. B. G. Cariaga), ferdinand.jamil@g.msuiit.edu.ph (F. Jamil) https://www.ejpam.com 847 © 2023 EJPAM All rights reserved. J. B.G. Cariaga, F. Jamil / Eur. J. Pure Appl. Math, 16 (2) (2023), 847-863 848 A set S ⊆ V (G) is said to be a dominating set of G if NG[S] = V (G). The minimum cardinality of a dominating set is called the domination number of G, and is denoted by γ(G). Any dominating set of cardinality γ(G) is referred to as a γ-set of G. We refer to [1, 3, 5, 7, 8, 12, 14] for the introduction, fundamental concepts and some studies on domination in graphs. A set S ⊆ V (G) is called a 2-dominating set if each v ∈ V (G)\S, |S∩NG(v)| ≥ 2. The 2-domination number of G, denoted γ2(G), is the minimum cardinality of a 2-dominating set of G. References [7, 10] provide a good study on 2-domination. 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 Roman dominating function of G. The history, introduction and some of the recent studies in Roman domination have been provided in [6, 13, 15–17]. A function f : V (G) → {0, 1, 2, 3} is a double Roman dominating function of G, written f ∈ DRD(G), if each of the following holds: (1) for each v ∈ V (G) with f(v) = 0 at least one of the following holds: (a) v has two adjacent vertices u and w for which f(u) = f(w) = 2; or (b) v has an adjacent vertex u for which f(u) = 3, and (2) for each v ∈ V (G) with f(v) = 1, v is adjacent to a vertex u for which either f(u) = 2 or f(u) = 3. The double Roman domination number of G, denoted by γdR(G), is the minimum weight ωG(f) = ∑ v∈V (G) f(v) of a double Roman dominating function f of G. Any f ∈ DRD(G) of weight equal to γdR(G) is referred to as γdR-function of G. The concept of double domination in graphs was proposed by Beeler, Haynes and Hedetniemi [2] in 2016. It is a stronger version of Roman domination. If in Roman domi- nation only one legion is required to defend an attacked city, in double Roman domination any attack can be defended by at least two legions. Double Roman domination is further studied in [9, 18, 19]. In this paper, the double Roman domination in graphs is revisited. The main interest is particularly on the double Roman dominating function of the join, corona, complementary prism and lexicographic product of graphs. The following results established in the referred articles are useful in this paper. Proposition 1. [2] In a double Roman dominating function of weight γdR(G), no vertex needs to be assigned the value 1. Proposition 2. [9] For n ≥ 1, γdR(Pn) = { n, if n ≡ 0 (mod 3), n+ 1, if n ≡ 1, 2 (mod 3). J. B.G. Cariaga, F. Jamil / Eur. J. Pure Appl. Math, 16 (2) (2023), 847-863 849 Proposition 3. [9] For n ≥ 3, γdR(Cn) = { n, if n ≡ 0, 2, 3, 4 (mod 6), n+ 1, if n ≡ 1, 5 (mod 6). Proposition 4. [2] For any graph G, 2γ(G) ≤ γdR(G) ≤ 3γ(G). 2. Results For a function f : V (G) → {0, 1, 2, 3}, we write f = (V0, V1, V2, V3), where Vi = {v ∈ V (G) : f(v) = i} for all i ∈ {0, 1, 2, 3}. Hence, f ∈ DRD(G) if and only if each of the following holds: (1) for each v ∈ V0, |V2 ∩NG(v)| ≥ 2 or |V3 ∩NG(v)| ≥ 1; and (2) for each v ∈ V1, either |V2 ∩NG(v)| ≥ 1 or |V3 ∩NG(v)| ≥ 1. In view of Proposition 1, we may always assume that a γdR-function of G is of the form f = (V0,∅, V2, V3). Thus, γdR(G) ≥ 2 for all graphs G. More precisely, γdR(G) = 2 if and only if G = K1. Proposition 5. Let G be a nontrivial connected graph. Then (i) γdR(G) = 3 if and only if γ(G) = 1; and (ii) γdR(G) = 4 if and only if γ(G) = 2 = γ2(G). Proof. If γdR(G) = 3 and f = (V0,∅, V2, V3) is a γdR-function of G, then V2 = ∅, |V3| = 1 and V0 = V (G) \ V3. If V3 = {v}, then NG[v] = V0 ∪ {v} = V (G). This means that γ(G) = 1. Conversely, if γ(G) = 1 and {v} is a dominating set ofG, then f = (V (G)\{v},∅,∅, {v}) ∈ DRD(G) so that γdR(G) ≤ ωG(f) = 3. Since G is nontrivial, γdR(G) = 3. This proves (i). Assume that γdR(G) = 4, and let f = (V0,∅, V2, V3) be a γdR-function of G. Then |V2| = 2 (say V2 = {u, v}), V3 = ∅ and V0 = V (G) \ {u, v}. Thus, V2 is a γ2-set so that γ2(G) = 2. Moreover, being a 2-dominating set, V2 is a dominating set of G so that γ(G) ≤ 2. By (i), γ(G) = 2. Conversely, let S = {u, v} be a γ2-set of G. Since f = (V (G) \ S,∅, S,∅) ∈ DRD(G), γdR(G) ≤ ωG(f) = 4. Because G is nontrivial and γ(G) ̸= 1, γdR(G) ≥ 4 by (i). Hence, γdR(G) = 4. This proves (ii). Proposition 6. For a nontrivial connected graph G, γdR(G) = 5 if and only if γ2(G) ≥ 3 and there exist u, v ∈ V (G) for which the following holds: (i) uv /∈ E(G); J. B.G. Cariaga, F. Jamil / Eur. J. Pure Appl. Math, 16 (2) (2023), 847-863 850 (ii) V (G) \NG[v] = {u} and V (G) \NG[u] ̸= {v}. Proof. Assume that γdR(G) = 5. In view of Proposition 5, γ2(G) ≥ 3. Let f = (V0,∅, V2, V3) be a γdR-function of G. Then |V2| = |V3| = 1. Let V2 = {u} and V3 = {v}. Since f is a γdR-function of G, NG(v) = V0. Because γ(G) ≥ 2, uv /∈ E(G). Hence, V (G) \NG[v] = {u}. Moreover, since γ2(G) ≥ 3, uw /∈ E(G) for some w ∈ V (G) \ {u, v}. Therefore, V (G) \NG[u] ̸= {v}. Conversely, suppose that γ2(G) ≥ 3, and let u, v ∈ V (G) such that uv /∈ E(G), V (G) \NG[v] = {u} and V (G) \NG[u] ̸= {v}. In view of Proposition 5, {u, v} is a γ-set of G. Since f = (V (G) \ {u, v},∅, {u}, {v}) ∈ DRD(G), γdR(G) ≤ ωG(f) = 5. Since γ(G) = 2 and γ2(G) ̸= 2, γdR(G) = 5 by Proposition 5. Corollary 1. For a nontrivial connected graph G, γdR(G) = 5 if and only if γ(G) = 2, γ2(G) ≥ 3 and γ(G− v) = 1 for some v ∈ V (G), where G− v is the resulting graph after removing the vertex v. Proof. Assume that γdR(G) = 5. By Proposition 6, γ2(G) ≥ 3 and there exist vertices u, v ∈ V (G) for which uv /∈ E(G), V (G) \ NG[u] = {v} and V (G) \ NG[v] ̸= {u}. This means that {u, v} and {u} are γ-sets of G and G − v, respectively. Thus, γ(G) = 2 and γ(G− v) = 1. Conversely, suppose that γ(G) = 2, γ2(G) ≥ 3 and let u, v ∈ V (G) such thatNG−v[u] = V (G − v). Since γ2(G) ̸= 2, there exists w ∈ V (G) \ {u, v} such that vw /∈ E(G). Thus, w ∈ V (G) \NG[u] so that V (G) \NG[v] ̸= {u}. Moreover, since γ(G) = 2, uv /∈ E(G) so that V (G) \NG[u] = {v}. By Proposition 6, γdR(G) = 5. Proposition 7. For nontrivial connected graph G, γdR(G) = 6 if and only if one of the following holds: (i) γ(G) = 2, γ2(G) ≥ 3 and γ(G− v) ≥ 2 for all v ∈ V (G). (ii) γ(G) ≥ 2 and γ2(G) = 3 and γ(G− v) ≥ 2 for all v ∈ V (G). Proof. Let γdR(G) = 6. Then γ(G) ≥ 2 by Proposition 5. Let f = (V0,∅, V2, V3) be a γdR-function of G. Consider the following cases: Case 1. Suppose that V2 = ∅ and |V3| = 2. Then V3 is a dominating set of G and so γ(G) = 2. Since γdR(G) ̸= 4, γ2(G) ≥ 3 by Proposition 5. Moreover, by Proposition 1, γ(G− v) ≥ 2 for all v ∈ V (G). This proves (i). Case 2. Suppose that |V2| = 3 and V3 = ∅. Then V2 is a 2-dominating set of G so that γ2(G) ≤ 3. Since γdR(G) ̸= 4, γ2(G) = 3 by Proposition 5. Hence, (ii) holds. Conversely, by Proposition 5, Proposition 6 and Corollary 1, γdR(G) ≥ 6. If u, v ∈ V (G) such that {u, v} dominates V (G), then f = (V (G) \ {u, v},∅,∅, {u, v}) ∈ DRD(G) so that γdR(G) ≤ ωG(f) = 6. On the other hand, if {u, v, w} is a γ2-set of G, then f = (V (G)\{u, v, w},∅, {u, v, w},∅) ∈ DRD(G) so that γdR(G) ≤ ωG(f) = 6. Therefore, each of (i) and (ii) implies that γdR(G) = 6. J. B.G. Cariaga, F. Jamil / Eur. J. Pure Appl. Math, 16 (2) (2023), 847-863 851 Proposition 8. For a nontrivial connected graph G, if γdR(G) = 7, then γ(G) = 3 and γ2(G) ≥ 4. Proof. Let γdR(G) = 7. By Proposition 5, Corollary 1, and Proposition 7, γ(G) ≥ 3 and γ2(G) ≥ 4 . Let f = (V0,∅, V2, V3) be a γdR-function of G. Then |V2| = 2 and |V3| = 1. Write V2 = {u, v} and V3 = {w}. Then {u, v, w} is a dominating set of G, and so, γ(G) ≤ 3. Hence, γ(G) = 3. The converse of Proposition 8 need not be true. Consider for example, the graph G in Figure 1 obtained from P9 = [x1, x2, x3, . . . , x9] by adding the edges x3x5 and x7x5. Observe that γ(G) = 3, γ2(G) ≥ 4 but γdR(G) = 9 > 7. .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... ............................................................................................................................................ ......... ............. ............. ............. ............. ............. ............. ............. ............. ............. ....... ..................................................................................................................................................................................................... ........... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .. ............................................................................................................................................................................. ........... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... ...... ..................................................................................................................................... ........................................................................................................ ............................................................................................................................................................................................................................. ................................................................ ............................................................... ............................................................... ............................... • • • x1 x2 x3 x4 x5 x6 x7 x8 x9 0 3 0 0 3 0 0 3 0 Figure 1: A graph G with γdR(G) > 7 Proposition 9. Let G be a disconnected graph with components C1, C2, . . ., Ck. Then γdR(G) = ∑k j=1 γdR(Cj). In particular, if G = Kn, then γdR(G) = 2n. Proof. If f1, f2, . . . , fk are γdR-functions of C1, C2, . . ., Ck, respectively, then the function f : V (G) → {0, 1, 2, 3} given by f(x) = fk(x) for all x ∈ V (Ck) is a γdR-function of G. Thus, γdR(G) ≤ ∑k j=1 γdR(Cj). Conversely, if f be a γdR-function of G, then the restriction f |Cj of f to Cj , for any j = 1, 2, . . . , k, is a γdR-function of Cj . Thus, γdR(Cj) ≤ ωCj (f |Cj ) for all j = 1, 2, . . . , k. Hence, ∑k j=1 γdR(Cj) ≤ γdR(G). Proposition 10. (i) For any path Pn of order n, γdR(Pn) =  2, n = 1; 4, n = 2; 5, n ≥ 3. (ii) For any cycle Cn of order n ≥ 3, γdR(Cn) = 6. Proof. For (i): The cases where n = 1, 2, 3, 4 are clear. Suppose that n ≥ 5. Let V (Pn) = [v1, v2, . . . , vn]. Then the sets {v1, v2} and {v1, v2, v3} are γ-set and γ2-set of Pn, respectively. Moreover, γ(Pn − v2) = 1. By Proposition 6, γdR(Pn) = 5. J. B.G. Cariaga, F. Jamil / Eur. J. Pure Appl. Math, 16 (2) (2023), 847-863 852 For (ii): The case where n = 3, 4 is clear. Suppose that n ≥ 5. Let u,w, v ∈ V (Cn) such that u,w ∈ NCn(v). Then {u, v} and {u, v, w} are γ-set and γ2-set of Cn, respectively. Moreover, γ(Cn − v) = 2 for all v ∈ V (Cn). By Proposition 7, γdR(Cn) = 6. The (n,m)-tadpole graph Tn,m is obtained by joining a cycle graph Cn and a path Pm with a bridge. The graph in Figure 2 is the tadpole T6,3. .................................... ............................................................................................................................................ ........................................................................................................ .................................... .......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... .... .................................... .......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... .... .................................... ........................................................................................................ ............................................................................................................................................ .................................... .................................... .................................... .................................................................................................................................................... ................................................................................................................ ................................................................................................................ .................................... Figure 2: The tadpole T6,3 Proposition 11. For Tn,1 with n ≥ 3, n ≤ γdR(Tn,1) ≤ n+ 1. More precisely, γdR(Tn,1) = { n, n ≡ 0, 3 (mod 6); n+ 1, n ≡ 1, 2, 4, 5 (mod 6). Proof. Let v ∈ V (Cn) be the vertex that connects Cn to P1 = {u} and let f = (V0,∅, V2, V3) be a γdR-function of Cn. We may assume that v /∈ V0. If v ∈ V3, then g = (V0 ∪ {u},∅, V2, V3) ∈ DRD(Tn,1). If v ∈ V2, then g = (V0, {u}, V2, V3) ∈ DRD(Tn,1). In any case, γdR(Tn,1) ≤ ωTn,1(g) ≤ 1 + γdR(Cn). Now, let f = (V0,∅, V2, V3) be a γdR-function of Tn,1. If v /∈ V0, then v ∈ V3 and u ∈ V0 so that g = (V0 \ {u},∅, V2, V3) ∈ DRD(Cn). If v ∈ V0 and u ∈ V2, then g = (V0 \ {v},∅, (V2 ∩ V (Cn)) ∪ {v}, V3) ∈ DRD(Cn). And, if v ∈ V0 and u ∈ V3, then g = (V0 \ {v},∅, V2, (V3 ∩ V (Cn)) ∪ {v}) ∈ DRD(Cn). In any case, γdR(Cn) ≤ ωCn(g) = γdR(Tn,1). Hence, the desired inequalities hold. Suppose that n ≡ 0, 3 (mod 6). Then γdR(Cn) = n (by Proposition 2.2.3) and Cn has a γdR-function f = (V0,∅, V2, V3) with V3 ̸= ∅. By symmetry, we assume that v ∈ V3. Thus, g = (V0 ∪ {u},∅, V2, V3) ∈ DRD(Tn,1). Together with the inequality, n ≤ γdR(Tn,1) ≤ ωTn,1(g) = γdR(Cn) = n. Therefore, γdR(Tn,1) = n. Suppose that n ≡ 2, 4 (mod 6). Then γdR(Cn) = n and V3 = ∅ for all γdR-functions f = (V0,∅, V2, V3) of Cn. With v ∈ V2, g = (V0, {u}, V2, V3) is a γdR-function of Tn,1. Thus, γdR(Tn,1) = n+ 1. J. B.G. Cariaga, F. Jamil / Eur. J. Pure Appl. Math, 16 (2) (2023), 847-863 853 Finally, suppose that n ≡ 1, 5 (mod 3). Then γdR(Cn) = n + 1 and Cn has a γdR- function f = (V0,∅, V2, V3) with V3 ̸= ∅. With v ∈ V3, g = (V0 ∪ {u},∅, V2, V3) ∈ DRD(Tn,1). Thus, n+ 1 = γdR(Cn) ≤ γdR(Tn,1) ≤ ωTn,1(g) = ωCn(f) = n+ 1. Proposition 12. Let n ≥ 3 and m ≥ 2. (i) If n ≡ 0, 3 (mod 6), then γdR(Tn,m) = { n+ 2, if m = 2 n+ γdR(Pm−1), if m ≥ 3. (ii) If n ≡ 2, 4 (mod 6), then γdR(Tn,m) =  n+ 2, if m = 2 n+ γdR(Pm), if m ≥ 3; m ≡ 0 (mod 3), n+ γdR(Pm)− 1, if m ≥ 3; m ≡ 1, 2 (mod 3). (iii) If n ≡ 1, 5 (mod 6), then γdR(Tn,m) = { n+ 3, if m = 2 n+ 1 + γdR(Pm−1), if m ≥ 3. Proof. Write Pm = [v1, v2, . . . , vm]. Let v ∈ V (Cn) be the vertex that connects Cn to Pm through the edge vv1. We consider the following cases: Case 1: Suppose that n ≡ 0, 3 (mod 6). Let f = (V0,∅, V2, V3) be a γdR-function of Cn with V3 ̸= ∅. Assume v ∈ V3. If m = 2, then g = (V0 ∪ {v1},∅, V2 ∪ {v2}, V3) is a γdR- function of Tn,2. Thus, γdR(Tn,2) = γdR(Cn)+2 = n+2. Assumem ≥ 3, and letm = 3k+r, where 0 ≤ r ≤ 2. Put V ∗ 3 = {v3j : j ∈ {1, 2, . . . , k}}. If 0 ≤ r ≤ 1, put V ∗ 0 = V (Pm) \ V ∗ 3 and V ∗ 2 = ∅. On the other hand, if r = 2, put V ∗ 0 = V (Pm) \ (V ∗ 3 ∪ {v3k+2}) and V ∗ 2 = {v3k+2}. Since (V ∗ 0 \ {v1},∅, V ∗ 2 , V ∗ 3 ) is a γdR-function of Pm − v1 ∼= Pm−1, g = (V0∪V ∗ 0 ,∅, V2∪V ∗ 2 , V3∪V ∗ 3 ) is a γdR-function of Tn,m. Thus, γdR(Tn,m) = n+γdR(Pm−1). Case 2: Suppose that n ≡ 2, 4 (mod 6). Let f = (V0, V1, V2, V3) be a γdR-function of Cn. Accordingly, V3 = ∅ and we may assume that v ∈ V2. If m = 2, then g = (V0 ∪ {v1},∅, V2 ∪ {v2},∅) is a γdR-function of Tn,2. Thus, γdR(Tn,2) = n+ 2. Suppose that m ≥ 3, and let m = 3k + r, where 0 ≤ r ≤ 2. Whenever r = 0, put V ∗ 3 = {v3j−1 : j ∈ {1, 2, . . . , k}}, V ∗ 0 = V (Pm) \ V ∗ 3 and V ∗ 2 = ∅. Then (V ∗ 0 ,∅, V ∗ 2 , V ∗ 3 ) is a γdR-function of Pm. Thus g = (V0 ∪ V ∗ 0 ,∅, V2 ∪ V ∗ 2 , V3 ∪ V ∗ 3 ) is a γdR-function of Tn,m. Consequently, γdR(Tn,m) = n+ γdR(Pm). Suppose that r = 1. Let j be the largest positive integer for which 2j ≤ 3k. If 2j = 3k, put V ∗ 2 = {v2i : i ∈ {1, 2, . . . , j − 1}}, V ∗ 0 = V (Pm) \ (V ∗ 2 ∪ {v3k}) and V ∗ 3 = {v3k}. On the other hand, if 2j < 3k, put V ∗ 2 = {v2i : i ∈ {1, 2, . . . , j}} ∪ {v3k+1}, V ∗ 0 = V (Pm) \ V ∗ 2 J. B.G. Cariaga, F. Jamil / Eur. J. Pure Appl. Math, 16 (2) (2023), 847-863 854 and V ∗ 3 = ∅. In either case, g = (V0 ∪ V ∗ 0 ,∅, V2 ∪ V ∗ 2 , V ∗ 3 ∪ V ∗ 3 ) is a γdR-function of Tn,m. Thus, γdR(Tn,m) = n+ γdR(Pm)− 1. Suppose that r = 2. Let j be the largest positive integer for which 2j ≤ 3k. If 2j = 3k, put V ∗ 2 = {v2i : i ∈ {1, 2, . . . , j + 1}}, V ∗ 0 = V (Pm) \ V ∗ 2 and V ∗ 3 = ∅. On the other hand, if 2j < 3k, put V ∗ 2 = {v2i : i ∈ {1, 2, . . . , j}}, V ∗ 0 = V (Pm) \ (V ∗ 2 ∪ {v3k+1}) and V ∗ 3 = {v3k+1}. In either case, g = (V0 ∪ V ∗ 0 ,∅, V2 ∪ V ∗ 2 , V ∗ 3 ∪ V ∗ 3 ) is a γdR-function of Tn,m. Thus, γdR(Tn,m) = n+ γdR(Pm)− 1. Case 3: Suppose that n ≡ 1, 5 (mod 6). Let f = (V0,∅, V2, V3) be a γdR-function of Cn with V3 ̸= ∅ and v ∈ V3. If m = 2, then g = (V0 ∪ {v1},∅, V2 ∪ {v2}, V3) is a γdR-function of Tn,2. Thus, γdR(Tn,2) = γdR(Cn) + 2 = n+ 1 + 2. Suppose that m ≥ 3, and let m = 3k + r, where 0 ≤ r ≤ 2. If r = 0, put V ∗ 3 = {v3j : j ∈ {1, 2, . . . , k}}, V ∗ 0 = V (Pm) \ V ∗ 3 and V ∗ 2 = ∅. If r = 1, put V ∗ 3 = {v3j : j ∈ {1, 2, . . . , k}}, V ∗ 0 = V (Pm) \ V ∗ 3 and V ∗ 2 = ∅. And if r = 2, put V ∗ 3 = {v3j : j ∈ {1, 2, . . . , k}}, V ∗ 0 = V (Pm)\(V ∗ 3 ∪ {v3k+2}) and V ∗ 2 = {v3k+2}. Since (V ∗ 0 \{v1},∅, V ∗ 2 , V ∗ 3 ) is a γdR-function of Pm − v1 ≡ Pm−1, g = (V0 ∪ V ∗ 0 ,∅, V2 ∪ V ∗ 2 , V3 ∪ V ∗ 3 ) is a γdR-function of Tn,m. Thus, γdR(Tn,m) = n + 1 + γdR(Pm−1). Let G and H be graphs with disjoint vertex sets. The join 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) ∪ {uv : u ∈ V (G), v ∈ V (H)}. Proposition 13. (join of graphs) Let G and H be nontrivial graphs. Then 3 ≤ γdR(G+H) ≤ 6. (1) More precisely, (i) γdR(G+H) = 3 if and only if γdR(G) = 3 or γdR(H) = 3. (ii) γdR(G+H) = 4 if and only if min{γdR(G), γdR(H)} = 4. (iii) γdR(G+H) = 5 if and only if min{γdR(G), γdR(H)} = 5. (iv) γdR(G+H) = 6 if and only if γdR(G) ≥ 6 and γdR(H) ≥ 6. Proof. Since G+H is nontrivial, γdR(G+H) ≥ 3. Now, let u ∈ V (G) and v ∈ V (G). Then f = (V (G + H) \ {u, v},∅,∅, {u, v}) ∈ DRD(G + H). Thus, γdR(G + H) ≤ ωG+H(f) = 6. To prove (i), we have from Proposition 5, γdR(G+H) = 3 ⇐⇒ γ(G+H) = 1 ⇐⇒ γ(G) = 1 or γ(H) = 1 J. B.G. Cariaga, F. Jamil / Eur. J. Pure Appl. Math, 16 (2) (2023), 847-863 855 ⇐⇒ γdR(G) = 3 or γdR(H) = 3. For (ii)-(iii), put α = min{γdR(G), γdR(H)}. Suppose that γdR(G + H) = 4. By Proposition 5, γ(G + H) = γ2(G + H) = 2. Let S = {u, v} be a γ2-set of G + H. If u ∈ V (G) and v ∈ V (H), then γ(G) = 1 and γ(H) = 1, a contradiction. Thus, S ⊆ V (G) or S ⊆ V (H). Consequently, γ(G) = γ2(G) = 2 or γ(H) = γ2(H) = 2. By Proposition 5, γdR(G) = 4 or γdR(H) = 4. By (i), α = 4. Conversely, suppose that α = 4, and let f be a γdR-function of G. Then g = (V0 ∪ V (H), V1, V2, V3) ∈ DRD(G+H) with ωG+H(g) = 4. Hence, γdR(G+H) ≤ ωG+H(g) = ωG(f) = 4. By (i), γdR(G+H) = 4. Suppose that the γdR(G+H) = 5. By (i) and (ii), α ≥ 5. It follows from Proposition 6 that γ(G+H) = 2, γ2(G+H) ≥ 3 and there exists v ∈ V (G+H) for which γ((G+H)−v) = 1. WLOG, assume that v ∈ V (G). Then γ(G − v) = 1 and, consequently, γ(G) = 2. If γ2(G) = 2, then γdR(G) = 4 by Proposition 5, a contradiction by (ii). Thus, γ2(G) ≥ 3 so that γdR(G) = 5. Thus, α ≤ 5. Conversely, assume α = γdR(G) = 5, and let f = (V0, V1, V2, V3) be a γdR-function of G. Then g = (V0 ∪ V (H), V1, V2, V3) ∈ DRD(G+H). Hence, γdR(G +H) ≤ ωG+H(g) = ωG(f) = 5 = α. But by (i) and (ii), γdR(G +H) ≥ 5. Therefore, γdR(G+H) = 5. Finally, (iv) follows immediately from Equation 1 and statements (i), (ii) and (iii). The complementary prism is the graph GG formed from G and its complement G by adding a perfect matching between corresponding vertices of G and G. If for each v ∈ V (G), v is the vertex in G corresponding to v, then GG is formed by adding the edge vv for every v ∈ V (G). Remark 1. (i) For any path Pn of order n ≥ 3, γdR(PnPn) = { 3 + n, if n ≡ 0 (mod 3), 3 + (n+ 1), if n ≡ 1, 2 (mod 3). (ii) For any cycle Cn of order n ≥ 3, γdR(CnCn) = { 4 + n, if n ≡ 1, 2, 3, 5 (mod 6); 5 + n, if n ≡ 0, 4 (mod 6). The following lemma is obvious. Lemma 1. For any graph G, γ(GG) = 1 if and only if G = K1. Proposition 14. Let G be a nontrivial graph. Then (i) γdR(G) ̸= 4; (ii) γdR(GG) = 3 if and only if G = K1; and J. B.G. Cariaga, F. Jamil / Eur. J. Pure Appl. Math, 16 (2) (2023), 847-863 856 (iii) γdR(GG) = 5 if and only if G = {K2,K2}. Proof. To prove (i), we claim that γ2(GG) ̸= 2. Suppose, in the contrary, that there exist u, v ∈ V (GG) such that S = {u, v} is a γ2-set of GG. If u, v ∈ V (G), then uv /∈ E(GG), a contradiction. Similar contradiction is attained if u, v ∈ V (G). Assume v ∈ V (G) and u ∈ V (G). If u = v, then for each w ∈ V (G) \ {v} either wv /∈ E(GG) or uw /∈ E(GG), a contradiction. Suppose that u ̸= v. A contradiction is already attained if uv /∈ E(G). However, if uv ∈ E(G), then uv /∈ E(G), a contradiction. Therefore, γ2(GG) ̸= 2. By Proposition 5, γdR(GG) ̸= 4. Clearly, if G = K1, then γdR(GG) = 3. Suppose that γdR(GG) = 3. Then γ(GG) = 1, by Proposition 5. Thus, by Lemma 1, G = K1. This proves (ii). Now, we prove (iii). If G ∈ {K2,K2}, then GG ∼= P4 so that γdR(GG) = 5. Conversely, assume γdR(GG) = 5. By (ii), G ̸= K1. Suppose that G /∈ {K2,K2}. Let u, v and w be distinct vertices of G. Then u,w ∈ V (GG)\NGG[v]. This means that |V (GG)\NGG[v]| ≥ 2 for all v ∈ V (G). Similarly, |V (GG) \ NGG[v]| ≥ 2 for all v ∈ V (G). Therefore, |V (GG) \ NGG[v]| ≥ 2 for all v ∈ V (GG). This is a contradiction to Proposition 6. Therefore, G ∈ {K2,K2}. Theorem 1. (complementary prism) Let G be a graph of order n ≥ 3. Assume γdR(G) ≤ γdR(G). Then 1 + γdR(G) ≤ γdR(GG) ≤ ρ, where ρ = min{ωG(f) + 2 (n− |V3|)− |V2| : f = (V0, V1, V2, V3) ∈ DRD(G) ∪DRD(G)}. Moreover, these bounds are sharp. Proof. Let f = (V0, V1, V2, V3) ∈ DRD(G). Extend f to a function on V (GG) by defining f(v) =  0, if v ∈ V3; 1, if v ∈ V2; 2, if v ∈ V0 ∪ V1. Then f ∈ DRD(GG) so that γdR(GG) ≤ ωG(f)+ 2 (n− |V3|)− |V2|. Thus, γdR(GG) ≤ ρ. Now, we show the left-hand inequality. Let f = (V0,∅, V2, V3) be a γdR-function of GG. If V (G) ⊆ V0, then V3 = V (G) so that γdR(GG) = 3|V3| = 3n ≥ 1 + γdR(G). Suppose that V (G) ∩ (V2 ∪ V3) ̸= ∅. Let A = {v ∈ V0 ∩ V (G) : V3 ∩ NGG(v) = {v}}, B = {v ∈ V0 ∩ V (G) : v ∈ V2 and |V2 ∩ NGG(v)| = 2} and C = {v ∈ V1 ∩ V (G) : (V2 ∪ V3)∩NGG(v) = {v}. Define g = (V ∗ 0 , V ∗ 1 , V ∗ 2 , V ∗ 3 ) on V (G) by g(x) =  f(x), if x ∈ V (G) \ (A ∪B ∪ C) ; 2, if x ∈ A ∪ C; 1, if x ∈ B. J. B.G. Cariaga, F. Jamil / Eur. J. Pure Appl. Math, 16 (2) (2023), 847-863 857 It follows that g ∈ DRD(G) with V ∗ 0 = (V0∩V (G))\(A ∪B), V ∗ 1 = B∪ [(V1 ∩ V (G)) \ C], V ∗ 2 = [V2 ∩ V (G)] ∪A ∪ C and V ∗ 3 = V3 ∩ V (G). Moreover, γdR(GG) = ωG(g) + ∑ x∈V (G) f(x)− 2|A| − |B| − |C| ≥ ωG(g) + 1 ≥ γdR(G) + 1. To show sharpness of the lower bound, note that by Proposition 14, γdR(K1K1) = 3 = 1 + γdR(K1). For the upper bound, pick G = Kn, n ≥ 3. Observe that γdR(GG) = 3 + 2(n− 1) = ρ. Corollary 2. Let G be a nontrivial graph with isolated vertex v. Then γdR(GG) = 3 + γdR(G− v). Proof. Let f be a γdR-function of G−v. Extend f to a function on V (GG) by defining f(v) = 3 and f(x) = 0 for all x ∈ V (G) ∪ {v}. Since f ∈ DRD(GG), γdR(GG) ≤ 3 + γdR(G− v). On the other hand, by Proposition 9, γdR(G) = 2+γdR(G−v). Thus, 3+γdR(G−v) = 1 + γdR(G) ≤ γdR(GG) by Theorem 1. Let G and H be graphs with disjoint vertex sets. 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 of the ith copy of H. For convenience, we write Hv to denote the copy of H joined to v and write Hv+v = Hv+⟨{v}⟩. If H = {u}, then V (Hv) = {uv}. Given a function f = (V0, V1, V2, V3) on V (G ◦ H), we write for each v ∈ V (G), V v i = Vi ∩ V (Hv) for all i = 0, 1, 2, 3. Observe also that ωG◦H(f) = ∑ v∈V (G) ωHv+v(f |Hv+v). Proposition 15. Let G be a nontrivial connected graph and H any graph, and let f = (V0, V1, V2, V3) be a function on V (G ◦H). Then f ∈ DRD(G ◦H) if and only if each of the following holds for f : (i) For each v ∈ (V0 ∪ V1)∩V (G), f |Hv ∈ DRD(Hv). Moreover, for each v ∈ V0∩V (G), if |V v 2 | = 1 and |V v 3 | = 0, then | (V2 ∪ V3) ∩NG(v)| ≥ 1. (ii) For each v ∈ V2 ∩ V (G), V v 2 ∪ V v 3 dominates V v 0 . Proof. Assume that f ∈ DRD(G ◦ H) and let v ∈ (V0 ∪ V1) ∩ V (G). To show that f |Hv ∈ DRD(Hv), first let u ∈ V v 0 . Note that NG◦H(u) = {v} ∪ NHv(u). If |V2 ∩NG◦H(u)| ≥ 2, then |V v 2 ∩NHv(u)| ≥ 2. On the other hand, if |V3 ∩NG◦H(u)| ≥ 1, then |V v 3 ∩ NHv(u)| ≥ 1. Next, let u ∈ V v 1 . Then there exists w ∈ V2 ∪ V3 such that w ∈ NG◦H(u). Necessarily, w ∈ V v 2 ∪ V v 3 and w ∈ NHv(u). Therefore, f |Hv ∈ DRD(Hv). J. B.G. Cariaga, F. Jamil / Eur. J. Pure Appl. Math, 16 (2) (2023), 847-863 858 Now, let v ∈ V0 ∩ V (G) and, suppose that |V v 2 | = 1 and V v 3 = ∅. If u ∈ V3 ∩NG◦H(v), then u ∈ V3 ∩NG(v). Suppose that |V2 ∩NG◦H(v)| ≥ 2. Since |V v 2 | = 1, |V2 ∩NG(v)| ≥ 1. This completely proves (i). To prove (ii), let v ∈ V2 ∩ V (G) and u ∈ V v 0 . Suppose there exists {w, z} ⊆ V2 ∩ NG◦H(u). If w = v, then z ∈ V v 2 and zu ∈ E(Hv). Suppose there exists w ∈ V3∩NG◦H(u). Then as w ̸= v, w ∈ V v 3 and wu ∈ E(Hv). This means that V v 2 ∪ V v 3 dominates V v 0 . Conversely, assume that (i) and (ii) all hold for f . Let u ∈ V0, and let v ∈ V (G) for which u ∈ V (Hv + v). First, suppose that u = v. If V v 3 ̸= ∅ and w ∈ V v 3 , then w ∈ V3 ∩NG◦H(u). Suppose that V v 3 = ∅. Since f |v ∈ DRD(Hv), V v 2 ̸= ∅. If |V v 2 | ≥ 2, then |V2∩NG◦H(u)| ≥ 2. Suppose that |V v 2 | = 1. By Condition (i), | (V2 ∪ V3)∩NG(v)| ≥ 1. This means that |V2 ∩NG◦H(u)| ≥ 2 or |V3 ∩NG◦H(u)| ≥ 1. Next, suppose that u ∈ V v 0 . If v ∈ V3, then |V3 ∩ NG◦H(u)| ≥ 1. If v ∈ V0 ∪ V1, then by Condition (i), |V v 2 ∩ NHv(u)| ≥ 2 or |V v 3 ∩ NHv(u)| ≥ 1. This means that |V2 ∩NG◦H(u)| ≥ 2 or |V3 ∩NG◦H(u)| ≥ 1. Now, suppose that v ∈ V2. By Condition (ii), there exists w ∈ V v 2 ∪ V v 3 for which w ∈ NHv(u). If w ∈ V v 3 , then |V3 ∩NG◦H(v)| ≥ 1. If w ∈ V v 2 , then {w, v} ⊆ V2 ∩NG◦H(u). Finally, let u ∈ V1. If u ∈ V (G), then since f |Hv ∈ DRD(Hu) (by (i)), V u 2 ∪ V u 3 ̸= ∅, say w ∈ V u 2 ∪ V u 2 . Then w ∈ (V1 ∪ V2) ∩ NG◦H(u). Suppose that u ∈ V (Hv) for some v ∈ V (G). If v ∈ V2 ∪ V3, then v ∈ (V1 ∪ V2) ∩ NG◦H(u). If v ∈ V0 ∪ V1, then as f |v ∈ DRD(Hv) (by (i)), there exists w ∈ V v 2 ∪ V v 3 such that w ∈ NHv(u). This means that w ∈ V2 ∪ V3 and w ∈ NG◦H(u). Therefore, f ∈ DRD(G ◦H). Corollary 3. Let G be a nontrivial connected graph of order n. Then (i) γdR(G ◦K1) = 3n−max{|V0| : f = (V0, V1, V2.V3) ∈ DRD(G)}. (ii) γdR(G ◦H) = 3n for all nontrivial graphs H. Proof. For (i): Let α = 3n − max{|V0| : f = (V0, V1, V2.V3) ∈ DRD(G)} and put V (K1) = {u}. Let f = (V0, V1, V2, V3) ∈ DRD(G) for which |V0| is maximum. Define V ∗ 0 = V0 ∪ {uv : v ∈ V3}, V ∗ 1 = V1 ∪ {uv : v ∈ V2}, V ∗ 2 = V2 ∪ {uv : v ∈ V0 ∪ V1} and V ∗ 3 = V3. By Proposition 15, g = (V ∗ 0 , V ∗ 1 , V ∗ 2 , V ∗ 3 ) ∈ DRD(G ◦K1). Thus, γdR(G ◦K1) ≤ 3(n− |V0|) + 2|V0| = 3n− |V0| = α. To get the other inequality, let f = (V0,∅, V2, V3) be a γdR-function of G◦K1. First, we claim that V2∩V (G) = ∅. Suppose not, and let w ∈ V2∩V (G). Since f is a γdR-function, uw ∈ V1, a contradiction to the choice of f . Next, we claim that f |G ∈ DRD(G). Let v ∈ V0 ∩ V (G). If uv ∈ V3, then g = (V0 \ {v}, {v, uv}, V2, V3 \ {uv}) ∈ DRD(G ◦K1) with ωG◦K1(g) = ωG◦K1(f) − 1, a contradiction. Thus, uv ∈ V2. Since V2 ∩ V (G) = ∅, there exists w ∈ V3∩V (G) for which vw ∈ E(G). Since V1∩V (G) = ∅, f |G = (V ∗ 0 , V ∗ 1 , V ∗ 2 , V ∗ 3 ) ∈ DRD(G) with V ∗ 0 = V0 ∩ V (G), V ∗ 1 = V ∗ 2 = ∅ and V ∗ 3 = V3. Observe also that for each J. B.G. Cariaga, F. Jamil / Eur. J. Pure Appl. Math, 16 (2) (2023), 847-863 859 v ∈ V (G), either uv ∈ V0 or uv ∈ V2. More precisely, uv ∈ V0 if and only if v ∈ V3 and uv ∈ V2 if and only if v ∈ V0. Thus γdR(G ◦K1) = ωG◦K1(f) = 3|V3|+ 2|V0 ∩ V (G)| = 3|V3|+ 3|V0 ∩ V (G)| − |V0 ∩ V (G)| = 3n− |V ∗ 0 | ≥ α. For (ii): By Proposition 15, f = (∪v∈V (G)V (Hv),∅,∅, V (G)) ∈ DRD(G ◦H). Thus, γdR(G ◦H) ≤ 3|V (G)| = 3n. On the other hand, if f = (V0, V1, V2, V3) ∈ DRD(G ◦ H), then ωHv+v(f |Hv+v) ≥ 3 for each v ∈ V (G). Thus, γdR(G ◦H) = ωG◦H(f) = ∑ v∈V (G) ωHv+v(f |Hv+v) ≥ 3n. The succeeding corollary, which are found in [19], are immediate consequences of Corol- lary 3(i). Corollary 4. [19] (i) γdR(Pn ◦K1) =  7n 3 , if n = 3k, 7n+2 3 , if n = 3k + 1, 7n+1 3 , if n = 3k + 2. (ii) γdR(Cn ◦K1) =  7n 3 , if n = 3k, 7n+2 3 , if n = 3k + 1, 7n+1 3 , if n = 3k + 2. (iii) γdR(Kn ◦K1) = 2n+ 1. (iv) γdR(Kp,q ◦K1) = { 2(p+ q) + 1, if p = 1 or q = 1, 2(p+ q + 1), otherwise. The lexicographic product of graphs G and H is the graph G[H] with V (G[H])= V (G) × V (H) and (u1, u2)(v1, v2) ∈ E(G[H]) if and only if either u1v1 ∈ E(G) or u1 = v1 and u2v2 ∈ E(H). J. B.G. Cariaga, F. Jamil / Eur. J. Pure Appl. Math, 16 (2) (2023), 847-863 860 For S ⊆ V (G[H]), we write SG = {x ∈ V (G) : (x, y) ∈ S for some y ∈ V (H)}. SG is referred to as the G-projection of S in G[H]. For a graph G, we define CG = {f = (V0,∅, V2, V3) ∈ DRD(G) : V2 \NG(V2 ∪ V3) = ∅}. Since f = (∅,∅, V (G),∅) ∈ CG, CG ̸= ∅. Proposition 16. Let G be a connected noncomplete graph and H any nontrivial graph with γ(H) = 1. Then γdR(G[H]) ≤ min{ωG(f) : f = (V0,∅, V2, V3) ∈ CG}. Moreover, this upper bound is sharp. Proof. Put α = min{ωG(f) : f = (V0,∅, V2, V3) ∈ CG}, and let v ∈ V (H) for which NH [v] = V (H). Let f = (V0,∅, V2, V3) ∈ CG. Put V ∗ 1 = ∅, V ∗ 2 = V2 × {v}, V ∗ 3 = V3 × {v} and V ∗ 0 = V (G[H])\(V ∗ 2 ∪ V ∗ 3 ). Let (x, y) ∈ V ∗ 0 . If x ∈ V3, then (x, v) ∈ V ∗ 3 ∩NG[H]((x, y)). Suppose that x ∈ V2. Then y ̸= v. Since f ∈ CG, there exists w ∈ V2 ∩ NG(x) or there exists z ∈ V3 ∩ NG(x). The former implies that (x, v), (w, v) ∈ V ∗ 2 ∩NG[Kp]((x, y)). The latter, on the other hand, implies that (z, v) ∈ V ∗ 3 ∩NG[Kp]((x, y)). Finally, suppose that x ∈ V0. Since f ∈ DRD(G), there exists u ∈ V3∩NG(x) or there exist distinct w, z ∈ V2 ∩NG(x). This means that (u, v) ∈ V ∗ 3 ∩NG[Kp]((x, y)) or we have distinct (w, v), (z, v) ∈ NG[H]((x, y)). Accordingly, g = (V ∗ 0 , V ∗ 1 , V ∗ 2 , V ∗ 3 ) ∈ DRD(G[H]). Moreover, ωG[H](g) = 2|V ∗ 2 |+ 3|V ∗ 3 | = 2|V2|+ 3|V3| = ωG(f). Therefore, γdR(G[H]) ≤ ωG(f). Since f is arbitrary, γdR(G[H]) ≤ α. To show sharpness, consider the lexicographic product of G = P4 = [v1, v2, v3, v4] and H = P3 as shown in Figure 3. We have for this case, γdR(G[H]) = 6 = ω(f), where f = ({v2, v3},∅,∅, {v1, v4}). The example presented in the proof of Proposition 16 also shows that min{ωG(f) : f = (V0,∅, V2, V3) ∈ CG} need not be determined by a γdR-function f of G. J. B.G. Cariaga, F. Jamil / Eur. J. Pure Appl. Math, 16 (2) (2023), 847-863 861 .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... ............................................................................................................................................................................................... ............................................................................................................................................................................................... ............................................................................................................................................................................................... ............................................................................................................................................................................................... ............................................................................................................................................................................................... ............................................................................................................................................................................................... ............................................................................................................................................................................................... ............................................................................................................................................................................................... ............................................................................................................................................................................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ .... ......... ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ .... ......... ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ .... ......... ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ .... ......... ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ .... ......... ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ .... ......... ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ .... ......... ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ .... ............................................................................................................................................................................................................................................. ............... .............. .............. .............. .............. .............. .............. .............. .............. .............. .............. .............. .............. .............. .............. .............. ............ ............... .............. .............. .............. .............. .............. .............. .............. .............. .............. .............. .............. .............. .............. .............. .............. ............ ............................................................................................................................................................................................................................................. ............................................................................................................................................................................................................................................. ............... .............. .............. .............. .............. .............. .............. .............. .............. .............. .............. .............. .............. .............. .............. .............. ............ ............... .............. .............. .............. .............. .............. .............. .............. .............. .............. .............. .............. .............. .............. .............. .............. ............ ............................................................................................................................................................................................................................................. ............... .............. .............. .............. .............. .............. .............. .............. .............. .............. .............. .............. .............. .............. .............. .............. ............ ............................................................................................................................................................................................................................................. ............... .............. .............. .............. .............. .............. .............. .............. .............. .............. .............. .............. .............. .............. .............. .............. ............ ............................................................................................................................................................................................................................................. ........... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... ........................................................................................................................................................................................................................................................................................................................................................... ........... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... ........................................................................................................................................................................................................................................................................................................................................................... .............................................................................................................................................................................................................................................................................................................................................................. .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... ........ • • 0 0 0 0 0 0 0 0 0 0 3 3 G[H] Figure 3: Graph G[H] where G = P4 and H = P3 Proposition 17. Let G be a connected noncomplete graph and p ≥ 2. Then γdR(G[Kp]) = min{ωG(f) : f = (V0,∅, V2, V3) ∈ CG}. Proof. Put α = min{ωG(f) : f = (V0,∅, V2, V3) ∈ CG}, and let v ∈ V (Kp). By Proposition 16, γdR(G[Kp]) ≤ α. To get the other inequality, let f = (V0, V1, V2, V3) be a γdR-function of G[Kp]. We assume that V1 = ∅. First, we claim the following: (i) (V2)G ∩ (V3)G = ∅; (ii) For each x ∈ (V2)G, |{y : (x, y) ∈ V2}| = 1; and (iii) For each x ∈ (V3)G, |{y : (x, y) ∈ V3}| = 1. For suppose that u ∈ (V2)G ∩ (V3)G, and let w ∈ V (Kp) for which (u,w) ∈ V2. Then f∗ ∈ DRD(G[Kp]), where f∗ is defined on V (G[Kp]) by f∗((x, y)) = f((x, y)) for all (x, y) ∈ V (G[Kp])\{(u,w)} and f∗((u,w)) = 0. This is a contradiction since ωG[Kp](f ∗) < ωG[Kp](f) and f is a γdR-function. This proves claim (i). To prove (ii), suppose that for some u ∈ (V2)G, we have (u,w), (u, t) ∈ V2. Then f∗ ∈ DRD(G[Kp]), where f∗ is defined on V (G[Kp]) by f∗((u,w)) = 3, f∗((u, t)) = 0 and f∗((x, y)) = f((x, y)) for all (x, y) ∈ V (G[Kp]) \ {(u,w), (u, t)}. Since ωG[Kp](f ∗) < ωG[Kp](f), this is a contradiction. Claim (iii) is clear. Let A = (V2)G, B = (V3)G and C = V (G) \ (A ∪B), and define V ∗ 0 = V (G[Kp]) \ ((A ∪B)× {v}), V ∗ 1 = ∅, V ∗ 2 = A × {v} and V ∗ 3 = B × {v}. De- fine the function g = (V ∗ 0 ,∅, V ∗ 2 , V ∗ 3 ) on V (G[Kp]). More specifically, g((x, y)) =  3, if x ∈ B and y = v, 2, if x ∈ A and y = v, 0, else REFERENCES 862 Let (x, y) ∈ V ∗ 0 . We consider the following cases: Case 1: Assume x ∈ A and y ̸= v. Since p ≥ 2, Claim (ii) implies that there exists w ∈ V (Kp) for which (x,w) ∈ V0. Thus, there exists (a, b) ∈ V3 ∩ NG[Kp]((x,w)) or there exist distinct (c, d), (e, f) ∈ V2 ∩ NG[Kp]((x,w)). If the former holds, then (a, v) ∈ V ∗ 3 ∩NG[Kp]((x, y)). Suppose the latter holds. By Claim (ii), c ̸= e so that we have distinct points (c, v), (e, v) ∈ V ∗ 2 ∩NG[Kp]((x, y)). We note here that it is possible to have x = c or x = e. Case 2: Assume x ∈ B and y ̸= v. Then (x, v) ∈ V ∗ 3 ∩NG[Kp]((x, y)). Case 3: Assume x ∈ (V0)G \ (A ∪ B). Then (x,w) ∈ V0 for all w ∈ V (Kp). Since f ∈ DRD(G[Kp]), there exists (a, b) ∈ V3 ∩NG[Kp]((x, y)) or there exist distinct (c, d), (e, f) ∈ V2 ∩ NG[Kp]((x, y)). If the former holds, then (a, v) ∈ V ∗ 3 ∩ NG[Kp]((x, y)). Suppose the latter holds. By Claim (ii), x, c and e are distinct vertices of G and (c, v), (e, v) ∈ V ∗ 2 ∩NG[Kp]((x, y)). All of the above imply that g ∈ DRD(G[Kp]). Since f is a γdR-function, ωG[Kp](g) = ωG[Kp](f). Thus, ωG[Kp](f) ≥ ωG[Kp](g) = 2|A|+ 3|B|. Now consider the function h = (C,∅, A,B) on V (G). Let x ∈ C. Then, in particular, (x, v) ∈ V ∗ 0 . Thus, there exists u ∈ B such that (u, v) ∈ NG[Kp]((x, v)) or there exist distinct w, z ∈ A for which (w, v), (z, v) ∈ NG[Kp]((x, v)). This means that there exists u ∈ B ∩ NG(x) or there exist distinct w, z ∈ A ∩ NG(x). Therefore, h ∈ DRD(G) with ωG(h) = 2|A|+3|B|. Let x ∈ A\NG(A∪B), and pick y ∈ V (Kp)\{v}. Then (x, y) ∈ V ∗ 0 . In view of Claim(iii), there exists (w, z) ∈ V ∗ 2 ∩ NG[Kp]((x, y)). This means that either w = x or w ∈ NG(x), a contradiction. Thus, A \ NG(A ∪ B) = ∅ and h ∈ CG. Finally, therefore, γdR(G[Kp]) ≥ ωG(h) ≥ α. Acknowledgements The authors would like to thank the referees for the invaluable assistance they gave us through their comments and suggestions which led to the improvement of the paper. Also, the authors would like to thank the Department of Science and Technology - Accelerated Science and Technology Human Resource Development Program (DOST-ASTHRDP)- Philippines, and MSU-Iligan Institute of Technology for funding this research. References [1] S. Arumugam and K. Karuppasamy. Fractional global domination in graphs. Discus- siones Mathematicae Graph Theory., 30:33–34, 2010. [2] R.A. Beeler, T.W. Haynes, and S.T. Hedetniemi. Double roman domination. Discrete Appl. Math., 211:23–29, 2016. REFERENCES 863 [3] C. Berge. Theory of graphs and its applications. Discrete Applied Mathematics., 1962. [4] F. Buckley and F. Harary. Distance in graphs. Redwood City, CA: Addison-Wesley., 1990. [5] E. J. Cockayne and S. T. Hedetniemi. Towards a theory of domination in graphs. Networks., 7:247–261, 1997. [6] E.J. Cockayne, P.M. Dreyer Sr., S.M. Hedetniemi, and S.T. Hedetniemi. Roman domination in graphs. Discrete Math., 278:11–22, 2004. [7] J.F. Fink, M.S. Jacobson, and in: Y. Alavi et al. (Eds.) n-domination in graphs. Graph theory with applications to algorithms and computer science. Wiley, New York., pages 283–300, 1985. [8] B. Gayathri and S. Kaspar. Connected co-independent domination of a graph. Int. J. Contemp. Math. Sciences., 6:423–429, 2011. [9] S.M. Sheikholeslami H. Abdollahzadeh Ahangar, M. Chellali. On the double roman domination in graphs. Discrete Appl. Math., pages 1–7, 2017. [10] A. Hansberg and L. Volkmann. On graphs with equal domination and 2-domination numbers. Discrete Mathematics., 308(11):2277–2281, 2008. [11] F. Harary. Graph theory. Addison-Wesley Publication Company, Inc., Mas- sachusetts., 1969. [12] F. Harary and T.W.Haynes. Double domination in graphs. Ars Combis., 55:201–213, 2000. [13] M.A. Henning and S.T. Hedetniemi. Defending the roman empire—a new strategy. Discrete Math., 266:239–251, 2003. [14] O. Ore. Theory of graphs. Amer. Math. Soc. Colloq. Publ., 1962. [15] L. Paleta and F. Jamil. More on perfect roman domination in graphs. European Journal of Pure and Applied Mathematics., 13(3):529–548, 2020. [16] C.S. ReVelle and K.E. Rosing. Defendens imperium romanum: a classical problem in military strategy. Amer. Math. Monthly., 107(7):585–594, 2000. [17] I. Stewart. Defend the roman empire!. Sci. Amer., 281(6):136–139, 1999. [18] Anu V. and Aparna Lakshmanan S. Double roman domination number. Discrete Appl. Math., 244:198–204, 2018. [19] Anu V. and Aparna Lakshmanan S. Impact of some graph operations on double roman domination number. 2018.