EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS Vol. 16, No. 3, 2023, 1705-1716 ISSN 1307-5543 – ejpam.com Published by New York Business Global Convex Roman Dominating Functions in a Graph Rona Jane G. Fortosa1,∗, Sergio R. Canoy, Jr.1,2 1 Department of Mathematics and Statistics, College of Science and Mathematics, MSU- Iligan Institute of Technology, 9200 Iligan City, Philippines 1 Center for Mathematical and Theoretical Physical Sciences - PRISM, MSU-Iligan Institute of Technology, 9200 Iligan City, Philippines Abstract. Let G be a connected graph. A function f : V (G) → {0, 1, 2} is a convex Roman dominating function (or CvRDF) if every vertex u for which f(u) = 0 is adjacent to at least one vertex v for which f(v) = 2 and V1 ∪ V2 is convex. The weight of a convex Roman dominating function f , denoted by ωCvR G (f), is given by ωCvR G (f) = ∑ v∈V (G) f(v). The minimum weight of a CvRDF on G, denoted by γCvR(G), is called the convex Roman domination number of G. In this paper, we determine the convex Roman domination numbers of some graphs and give some realization results involving convex Roman domination, connected Roman domination, and convex domination numbers. 2020 Mathematics Subject Classifications: 05C69 Key Words and Phrases: Convex set, Roman dominating function, Roman domination number, convex Roman dominating function, convex Roman domination number 1. Introduction The concept Roman domination was first introduced by Cockayne, Dreyer and Hedetnieme in 2004 [11] as a variant of dominating set problem in graph theory. Roman domination is inspired by the ancient Roman Empire’s military strategy, where soldiers would be stationed at strategic points throughout a location to ensure its protection. In the Roman domination strategy, an unsecured location can be secured by sending an army to the location from an adjacent secured location subject to the constraint that one army must be left behind the secured location. Specifically, in this protection strategy, a vertex with label (or image under a function) 1 or 2 may be viewed as one or two armies, respec- tively, stationed at the given location or vertex. A nearby location (an adjacent vertex) is considered to be unsecured if no armies are stationed there, that is if the label of the vertex is 0. The convex Roman domination strategy in addition ensures that all locations that lie along shortest paths between any two secured locations are also secured. ∗Corresponding author. DOI: https://doi.org/10.29020/nybg.ejpam.v16i3.4828 Email addresses: ronajane.fortosa@g.msuiit.edu.ph (R.J. Fortosa), sergio.canoy@g.msuiit.edu.ph (S. Canoy) https://www.ejpam.com 1705 © 2023 EJPAM All rights reserved. R. Fortosa, S. Canoy Jr. / Eur. J. Pure Appl. Math, 16 (3) (2023), 1705-1716 1706 Since then, Roman domination function has become a popular topic of study in graph theory, and several variations and related concepts have been studied. Some variations can be found in [1], [2], [3], [4], [5], [10], [11], [13], [14], [18], and [17]. One of the fundamental concepts in mathematics that has been studied extensively in geometry and has been extended to graphs is convexity. Convexity in graphs is discussed in the book of Buckley and Harary [6]. Some studies on convexity in graphs and its related concepts can be found in [7], [8], [9], [12], [15], [16], and [19]. In this paper, we introduce the concept of convex Roman domination on which we combine the notions of convexity and Roman domination. Let G be a connected graph. For vertices u and v in G, a u-v geodesic is any shortest path in G joining u and v. The length of a u-v geodesic is called the distance dG(u, v) between u and v. For every two vertices u and v of G, the symbol IG[u, v] is used to denote the set of vertices lying on any of the u-v geodesics. The set of neighbors of a vertex u ∈ G, denoted by NG(u), is called the open neighborhood of u. The closed neighborhood of u is the set NG[u] = NG(u) ∪ {u}. The degree of a vertex v denoted degG(v) in a graph G is the number of vertices in G that are adjacent to v. Hence, degG(v) = |N(v)|. The largest degree among the vertices of G is called the maximum degree of G and is denoted by △(G). The minimum degree of G is denoted by δ(G). A graph G is connected if every pair of its vertices can be joined by a path. A vertex of a connected graph G is an extreme vertex or simplicial if its open neighborhood induces a complete subgraph of G. The set of extreme vertices of G is denoted by Ext(G). A set S ⊆ V (G) is said to be a dominating set of a graph G if every vertex v ∈ V (G) is either an element of S or is adjacent to an element of S. Thus, N [S] = V (G). The smallest cardinality of a dominating set S is called the domination number of G and is denoted by γ(G). That is γ(G) = min{|S| : S is a dominating set of G}. Any dominating set S of G with |S| = γ(G) is called a γ-set of G. A set S ⊆ V (G) is convex if for every two vertices x, y ∈ S, IG[x, y] ⊆ S. The largest cardinality of a proper convex set in G, denoted by con(G), is called the convexity number of G. A set S ⊆ V (G) is convex dominating if S is both convex and dominating. The minimum cardinality among all convex dominating sets in G, denoted by γcon(G) is called the convex domination number of G. A function f : V (G) → {0, 1, 2} is a Roman dominating function (or just RDF) if every vertex u for which f(u) = 0 is adjacent to at least one vertex v for which f(v) = 2. The weight of an RDF f is given by ωG(f) = ∑ v∈V (G) f(v). The Roman domination number of a graph G, denoted by γR(G), is the minimum weight of an RDF in G. Any RDF f on G with ωG(f) = γR(G) is called a γR-function. If f = (V0, V1, V2) is an RDF in G, then ωG(f) = |V1|+ 2|V2|. A function f = (V0, V1, V2) is called connected Roman dominating function (CRDF) in G if ⟨V1 ∪ V2⟩ is connected. The weight of a connected Roman dominating function f = (V0, V1, V2) in G is given by ωCR G (f) = |V1|+2|V2|. The connected Roman domination number γCR(G) is the minimum weight of a CRDF in G. Any CRDF f in G with ωCR G (f) = γCR(G) is called a γCR-function. R. Fortosa, S. Canoy Jr. / Eur. J. Pure Appl. Math, 16 (3) (2023), 1705-1716 1707 A Roman dominating function f = (V0, V1, V2) on G is a convex Roman dominating function (or CvRDF) if V1 ∪ V2 is convex. The weight of a convex Roman dominating function f = (V0, V1, V2) in G is given by ωCvR G (f) = |V1|+2|V2|. The minimum weight of a CvRDF on G, denoted by γCvR(G), is called the convex Roman domination number of G. Any CvRDF f in G with ωCvR G (f) = γCvR(G) is called a γCvR-function. A complete k-partite graph G is a k-partite graph with partite sets Sn1 , Sn2 , . . . , Snk having the added property that if u ∈ Sni and v ∈ Snj , i ̸= j, then uv ∈ E(G). If |Sni | = ni, then this graph is denoted by Kn1,n2,...,nk . The join of two graphs G and H, denoted by G + H, is the graph with V (G+H) = V (G)∪V (H) and E(G+H) = E(G)∪E(H)∪{uv : u ∈ V (G) and v ∈ V (G)}, where “∪” refers to a disjoint union of sets. 2. Known Results Cyman et al. [19] investigated those graphs which have convex domination number close to their orders. They generated the following results which will be used in this study. Theorem 1. Let G be a connected graph with n ≥ 5. If γcon(G) = n, then △(G) ≤ n− 4. Corollary 1. If γcon(G) = n and G ̸= K1, then 2 ≤ δ(G) ≤ △(G) ≤ n− 4. Corollary 2. If γcon(G) = n and G ̸= K1, then n ≥ 6. 3. Results It is well-known that every convex set in a connected graph induces a connected graph. Remark 1. Every convex Roman dominating function is a connected Roman dominating function. Hence, γCvR(G) ≥ γCR(G). The next result shows that every pair of positive integers are realizable as the connected Roman domination number and convex Roman domination number of a connected graph. Theorem 2. Let a and b be positive integers such that 4 ≤ a ≤ b. Then there exists a connected graph G such that γCR(G) = a and γCvR(G) = b. Proof. Consider the following cases: Case 1. a = b. Let G = Ca. Then γCR(G) = γCvR(G) = a. Case 2. a < b. Letm = b−a. Consider the graphG in Figure 1. Let V0 = {x1, x2, . . . , xm}, V1 = {v1, v2, . . . , va−2}, V2 = {va−1}, V ′ 0 = ∅, V1 = {x1, x2, . . . , xm, v1, v2, . . . , va−2}, V2 = {va−1}. Then f = (V0, V1, V2) is a γCR-function and g = (V ′ 0 , V ′ 1 , V ′ 2) is a γCvR- function on G. Hence, γCR(G) = ωCR G (G) = |V1|+ 2|V2| = a− 2 + 2(1) = a and γCvR(G) = ωCvR G (G) = |V ′ 1 |+ 2|V ′ 2 | = m+ (a− 2) + 2(1) = b. R. Fortosa, S. Canoy Jr. / Eur. J. Pure Appl. Math, 16 (3) (2023), 1705-1716 1708 v1 v2 v3 · · · va−4 va−3 va−2 va−1 x1 x2 ... xm Figure 1: A graph with γCR(G) = a and γCvR(G) = b This proves the assertion. Corollary 3. Let n be a positive integer. Then there exists a connected graph G such that γCvR(G) − γCR(G) = n. In other words, the difference γCvR(G) − γCR(G) can be made arbitrarily large. Remark 2. If f = (V0, V1, V2) is a γCvR-function, then V1 ∪ V2 need not be a γcon-set. To see this, consider P4 = [v1, v2, v3, v4]. Let V0 = {v1}, V1 = {v3, v4}, and V2 = {v2}. Then f = (V0, V1, V2) is a γCvR-function on P4. Clearly, V1 ∪ V2 is not a γcon-set in P4. Proposition 1. For any connected graph G of order n, 1 ≤ γcon(G) ≤ γCvR(G) ≤ min{n, 2γcon(G)}. Proof. Let f = (V0, V1, V2) be a γCvR-function. Then V1 ∪ V2 is a convex dominating set in G. Hence, 1 ≤ γcon(G) ≤ |V1|+ |V2| ≤ |V1|+ 2|V2| = γCvR(G). Now, let V ′ 0 = V ′ 2 = ∅ and V ′ 1 = V (G). Then g = (V ′ 0 , V ′ 1 , V ′ 2) is a CvRDF and γCvR(G) ≤ |V ′ 1 | = |V (G)| = n. Next, let S be a γcon-set of G. Define h = (V ′′ 0 , V ′′ 1 , V ′′ 2 ) by setting V ′′ 2 = S, V ′′ 0 = V (G) \ S, and V ′′ 1 = ∅. Then h is a CvRDF on G. Hence, γCvR(G) ≤ ωCvR G (G) = 2|S| = 2γcon(G). Therefore, γCvR(G) ≤ min{n, 2γcon(G)}. Theorem 3. Let G be a connected graph on n vertices. Then each of the the following statements holds. (i) γCvR(G) = 1 if and only if G = K1 (ii) γCvR(G) = 2 if and only if G = K1 +H for some graph H Proof. (i) Assume that γCvR(G) = 1 and let f = (V0, V1, V2) be a γCvR-function on G. Then |V1| = 1 and |V2| = 0. Hence G = K1. The converse is clear. R. Fortosa, S. Canoy Jr. / Eur. J. Pure Appl. Math, 16 (3) (2023), 1705-1716 1709 (ii) Suppose that γCvR(G) = 2 and let f = (V0, V1, V2) be a γCvR-function on G. Then ωCvR G (f) = |V1|+ 2|V2| = 2. Consider the following cases: Case 1. |V1| ≠ 0 Then |V2| = 0 and |V1| = 2, say V1 = {a, b}. Since V1 is convex, ab ∈ E(G). Since |V2| = 0, |V0| = 0. Hence, V (G) = V1, that is G = K2 = K1 +K1. Case 2. |V1| = 0 Then |V2| = 1 since 2|V2| = 2. If n = 2, then G = K2. Suppose n ≥ 3. Let V2 = {u} and let w ∈ V (G) \ V2. Then w ∈ V0, that is V0 = V (G) \ V2. This implies that uw ∈ E(G) for all w ∈ V (G) \ V2. Hence, G = ⟨{u}⟩ + ⟨V (G) \ {u}⟩. Let H = ⟨V (G) \ {u}⟩. Then G = K1 +H. Conversely, suppose that G = K1 +H for some graph H. Define g = (V ′ 0 , V ′ 1 , V ′ 2) by setting V ′ 0 = V (H), V ′ 1 = ∅ and V ′ 2 = V (K1). Then g is a γCvR-function on G and ωCvR G (g) = γCvR(G) = |V1|+ 2|V2| = 2. Theorem 3(ii) can be rephrased as follows: Corollary 4. For any connected graph G of order n, γCvR(G) = 2 if and only if G ̸= K1 and γ(G) = 1. In particular, (i) γCvR(Kn) = 2 for n ≥ 2; (ii) γCvR(Fn) = 2 for n ≥ 1; (iii) γCvR(Wn) = 2 for n ≥ 3; and (iv) γCvR(Sn) = γCvR(K1,n−1) = 2 for n ≥ 2. Proposition 2. There exists no connected graph G with γCvR(G) = 3. Proof. Suppose G is a connected graph with γCvR(G) = 3. Let f = (V0, V1, V2) be a γCvR-function on G. Then γCvR(G) = |V1| + 2|V2| = 3. This implies that |V2| ≤ 1. Suppose |V2| = 0. Then |V0| = 0 and |V1| = |V (G)| = 3. Hence, G = K3 or G = P3. However, γCvR(K3) = γCvR(P3) = 2, a contradiction. Next, suppose that |V2| = 1. Then |V1| = 1. Let V1 = {w} and V2 = {v}. Since V1 ∪ V2 is convex, vw ∈ E(G). Also, since V0 ⊆ NG(v), V2 is a dominating set in G. Hence, γ(G) = 1, implying that γCvR(G) = 2, a contradiction. This proves the claim. Proposition 3. Let G be a nontrivial connected graph and let f = (V0, V1, V2) be a γCvR- function on G. Then the following hold: (i) If |V0| = 0, then |V2| = 0. (ii) If |V0| = 1, then |V2| = 1. (iii) |V1| = 0 if and only if V2 is a γcon-set in G (hence, γCvR(G) = 2γcon(G)). R. Fortosa, S. Canoy Jr. / Eur. J. Pure Appl. Math, 16 (3) (2023), 1705-1716 1710 Proof. (i) Suppose |V2| ̸= 0. Let V ′ 0 = V0, V ′ 1 = V1 ∪ V2 and V ′ 2 = ∅. Then g = (V ′ 0 , V ′ 1 , V ′ 2) is a CvRDF on G and ωCvR G (g) = |V ′ 1 | = |V1| + |V2| < |V1| + 2|V2| = ωCvR G (f), a contradiction. (ii) Suppose |V0| = 1, say V0 = {v0}. Suppose further that |V2| ≥ 2. Then V (G) \ {v0} is a convex dominating set in G. Let v ∈ V2 such that v0v ∈ E(G). Let w ∈ V2 \{v}. Let h = (V0, V ′ 1 , V ′ 2), where V ′ 1 = V1∪{w} and V ′ 2 = V2\{w}. Since V ′ 1∪V ′ 2 = V1∪V2, h is a convex Roman dominating function on G and ωCvR G (h) = |V ′ 1 |+ 2|V ′ 2 | = |V1|+ 1 + 2(|V2| − 1) = |V1|+ 2|V2| − 1 < ωCvR G (f), a contradiction. Thus, |V2| = 1. (iii) Suppose |V1| = 0. Suppose further that V2 is not a γcon-set in G. Then there exists V ′ 2 ⊆ V (G) such that V ′ 2 is a convex dominating set in G with |V ′ 2 | < |V2|. Let h = (V ∗ 0 , V ∗ 1 , V ∗ 2 ), where V ∗ 1 = ∅, V ∗ 2 = V ′ 2 , and V ∗ 0 = V (G)\V ′ 2 . Then h is a convex Roman dominating function on G and ωCvR G (h) = 2|V ∗ 2 | < 2|V2|, a contradiction. Thus, V2 is a γcon-set in G. Conversely, suppose that V2 is a γcon-set in G. Suppose |V1| ≠ 0. Then γCvR(G) = |V1| + 2|V2| > 2|V2|. Let V ′′ 0 = V0 ∪ V1, V ′′ 1 = ∅, and V ′′ 2 = V2. Then V ′′ 0 ⊆ NG(V ′′ 2 ) and V ′′ 1 ∪ V ′′ 2 = V2 is a convex dominating set in G. Thus, h = (V ′′ 0 , V ′′ 1 , V ′′ 2 ) is a CvRDF on G and ωCvR G (h) = 2|V2| < ωCvR G (f), contrary to our assumption of f . We now show that every pair of positive integers under some restrictions are realizable as the convex domination number and convex Roman domination number of a connected graph. Theorem 4. Let a and b be positive integers such that 4 ≤ a + 2 ≤ b ≤ 2a. Then there exists a connected graph G such that γcon(G) = a and γCvR(G) = b. Proof. Suppose b = 2a. Consider the graph G′ in Figure 2. Let S = {v1, v2, v3, . . . , va}. Put V2 = S, V1 = ∅, and V0 = V (G′) \ V2. Clearly, S is γcon-set and f = (V0, V1, V2) is a γCvR-function on G′. Thus, γcon(G ′) = |S| = a and γCvR(G ′) = 2|V2| = 2a = b. v1 v2 v3 · · · va−1 va Figure 2: A graph G′ with γcon(G ′) = a and γCvR(G ′) = 2a R. Fortosa, S. Canoy Jr. / Eur. J. Pure Appl. Math, 16 (3) (2023), 1705-1716 1711 Next, let b < 2a. Then 2 ≤ m = b − a < a. Consider the graph G in Figure 3. Let S∗ = {v1, v2, . . . , va}. Then S∗ is a γcon-set in G. It follows that γcon(G) = a. Set V2 = {v1, v2, . . . , vm−1, va}, V1 = {vm, vm+1, . . . , va−1}, and V0 = V (G)\(V1∪V2). Clearly, g = (V0, V1, V2) is a γCvR-function on G. Therefore, γCvR(G) = |V1|+ 2|V2| = (a−m) + 2m = m+ a = b. v1 v2 v3 · · · vm−1 vm · · · va−1 va Figure 3: A graph G with γcon(G) = a and γCvR(G) = b < 2a This proves the assertion. Corollary 5. Let n be a positive integer with n ≥ 2. Then there exists a connected graph G such that γCvR(G) − γcon(G) = n. In other words, the difference γCvR(G) − γcon(G) can be made arbitrarily large. Proposition 4. Let n be a positive integer. Then γCvR(Pn) =  1 if n = 1 2 if n = 2, 3 n if n ≥ 4. Proof. Clearly, γCvR(P1) = 1 and γCvR(Pn) = 2 for n = 2, 3. Suppose n ≥ 4. Let Pn = [v1, v2, . . . , vn] and let f = (V0, V1, V2) be a γCvR-function on Pn. If |V0| = 0, |V2| = 0 by Proposition 3(i). It follows that V1 = V (Pn) and γCvR(Pn) = ωCvR Pn (f) = |V1| = n. Suppose there exists vj ∈ V0 such that j ̸= 1, n. Then vj−1 ∈ V2 or vj+1 ∈ V2. If vj−1 ∈ V2, then vk ∈ V0 for all k > j since V1 ∪ V2 is convex. Again, by convexity in V1 ∪ V2, vs ∈ V0 for all s < j whenever vj+1 ∈ V2. In either case, f is not an RDF in G, a contradiction. Therefore, V0 ⊆ {v1, vn}. Suppose V0 = {v1} (or {vn}). Since f is a γCvR-function, V2 = {v2} (resp. {vn−1}) and V1 = V (Pn) \ {v1, v2} (resp. V (Pn) \ {vn−1, vn}). Hence, γCvR(Pn) = ωCvR Pn (f) = |V1| + 2|V2| = n. Suppose V0 = {v1, vn}. Then V2 = {v2, vn−1} and V1 = V (Pn) \ {v1, v2, vn−1, vn}. Hence γCvR(Pn) = ωCvR Pn = |V1|+ 2|V2| = n. Proposition 5. Let n be a positive integer with n ≥ 3. Then γCvR(Cn) = { 2 if n = 3 n if n ≥ 4. R. Fortosa, S. Canoy Jr. / Eur. J. Pure Appl. Math, 16 (3) (2023), 1705-1716 1712 Proof. Clearly, γCvR(C3) = 2. Suppose that n ≥ 4. Let Cn = [v1, v2, . . . , vn, v1] and let g = (V0, V1, V2) be a γCvR-function on Cn. If V0 = ∅, then V2 = ∅, by Proposition 3(i). Hence, γCvR(Cn) = n. Suppose V0 ̸= ∅. Since V1 ∪ V2 is convex, ⟨V0⟩ is connected. Hence, |V0| ≤ 2. Let n = 4. Suppose |V0| = 1. Assume without loss in generality that V0 = {v1}. Then V1 ∪ V2 = {v2, v3, v4} which is not convex, a contradiction. Hence |V0| = 2. Again, we may assume that V0 = {v1, v2}. Then V2 = {v3, v4}. It follows that γCvR(C4) = 2|V2| = 4. Let n = 5. By convexity in V1∪V2, it can be verified that |V0| = 2. This implies that |V2| = 2 and |V1| = 1. Thus, γCvR(C5) = |V1| + 2|V2| = 5. Suppose n ≥ 6. Suppose |V0| = 2, say V0 = {v1, v2}. Then [v3, v2, v1, vn] is a v3-vn geodesic in Cn, implying that V1 ∪ V2 is not convex. This is a contradiction to the assumption that g is a CvRDF. Therefore, |V0| = 1. Since g is a γCvR-function, |V2| = 1 and |V1| = n− 2. Thus, γCvR(Cn) = n. Proposition 6. Let G = Kn1,...,nk be the complete k-partite graph with 2 ≤ n1 ≤ n2 . . . ≤ nk where k ≥ 2. Then γCvR(G) = 4. Proof. Let Sn1 , Sn2 , . . . , Snk be the partite sets in G. Let i, j ∈ {1, 2, . . . , k} with i ̸= j. Choose any u ∈ Sni and w ∈ Snj . Put V2 = {u,w}, V0 = V (G) \ V2, and V1 = ∅. Then f = (V0, V1, V2) is a CvRDF on G. Thus, γCvR(G) ≤ ωCvR G (f) = 2|V2| = 4. Suppose γCvR(G) < 4. Let g = (V ′ 0 , V ′ 1 , V ′ 2) be a γCvR-function on G. Then γCvR(G) = ωCvR G (g) = |V ′ 1 | + 2|V ′ 2 | < 4. This implies that |V ′ 2 | ≤ 1. If |V ′ 2 | = 0, then |V ′ 0 | = 0 and |V ′ 1 | = |V (G)| ≥ 4, a contradiction. Thus, |V ′ 2 | = 1. If ωCvR G (g) = 2, then |V ′ 1 | = 0. Let V ′ 2 = {p}, where p ∈ Snj for j ∈ {1, 2, . . . , k}. Pick any q ∈ Snj \ {p}. Since |V ′ 2 | = 1, q ∈ V0. This is not possible because pq /∈ E(G). This forces ωCvR G (g) = 3 which is also not possible by Proposition 2. Therefore, γCvR(G) = 4. Proposition 7. Let G be a connected non-complete graph and let f = (V0, V1, V2) be a γCvR-function on G. If |V1| = 0, then the following hold: (i) every cut-vertex belongs to V2, (ii) no extreme vertex belongs to V2, and (iii) for any u, v ∈ V2 such that dG(u, v) ≥ 2, NG(u) ∩NG(v) ⊆ V2. Proof. Since |V1| = 0, V2 is a γcon-set in G by Proposition 3(iii). Suppose there exists a cut-vetex v of G such that v /∈ V2. Let G1 and G2 be distinct components of G \ v. Pick any p ∈ V2∩V (G1) and q ∈ V2∩V (G2). Since every p-q geodesic contains v, it follows that V2 is not convex, a contradiction. Hence, (i) holds. Suppose there exists w ∈ Ext(G)∩V2. Since G ̸= Kn, there exists z ∈ NG(w) such that y ∈ NG(z) \ NG(w). Suppose z ∈ V0. Then there exists x ∈ NG(z) ∩ V2. Since V2 is γcon-set, x /∈ NG(w). Hence, [x, z, w] is a x-w geodesic, contrary to the fact that V2 is convex. Hence, z ∈ V2. Again, this is not possible because V2 is a γcon-set. Therefore, w /∈ V2. Thus, (ii) holds. Next, let u, v ∈ V2 such that dG(u, v) ≥ 2. If dG(u, v) > 2, then NG(u) ∩NG(v) = ∅, then we are done. Suppose dG(u, v) = 2 and let a ∈ NG(u) ∩NG(v). By convexity of V2, it follows that a ∈ V2, showing that NG(u)∩NG(v) ⊆ V2. This shows that (iii) holds. R. Fortosa, S. Canoy Jr. / Eur. J. Pure Appl. Math, 16 (3) (2023), 1705-1716 1713 Proposition 8. Let G be a conneted graph of order n. Then γcon(G) = γCvR(G) if and only if γcon(G) = n. Proof. If γcon(G) = n, then γCvR(G) = n by Proposition 1. For the converse, suppose that γcon(G) = γCvR(G). Let f = (V0, V1, V2) be a γCvR-function on G. Then γcon(G) ≤ |V1|+ |V2| ≤ |V1|+ 2|V2| = γCvR(G). By assumption, this implies that |V2| = 0. Hence, |V0| = 0, implying that γcon(G) = |V1| = n = γCvR(G). The next two results follow from Proposition 8, Theorem 1, Corollary 1, and Corollary 2. Corollary 6. Let G be a connected graph of order n. If γcon(G) = γCvR(G) and G ̸= K1, then 2 ≤ δ(G) ≤ △(G) ≤ n− 4. Corollary 7. Let G be a nontrivial connected graph of order n. If γcon(G) = γCvR(G), then n ≥ 6. Theorem 5. Let G be a nontrivial connected graph on n vertices such that γcon(G) < γCvR(G). Then γCvR(G) = γcon(G) + 1 if and only if there exist a vertex v and a set S ⊆ V (G) such that S ⊆ NG(v) and V (G) \ S is a γcon-set in G. Proof. Suppose γCvR(G) = γcon(G) + 1. Let f = (V0, V1, V2) be a γCvR-function on G. Since V1 ∪ V2 is a convex dominating set in G, γcon(G) ≤ |V1| + |V2|. Consider the following cases: Case 1. γcon(G) = |V1|+ |V2|. Then γcon(G) + 1 = |V1| + |V2| + 1. By assumption, |V1| + |V2| + 1 = |V1| + 2|V2|. This implies that |V2| = 1 and |V1| = γcon(G)− 1. Let V2 = {v} and S = V0. Then S ⊆ NG(v). Since V1 ∪ V2 is a convex dominating set in G and |V1 ∪ V2| = γcon(G), it follows that V (G) \ S = V1 ∪ V2 is a γcon-set in G. Case 2. γcon(G) < |V1|+ |V2|. Then γcon(G)+1 ≤ |V1|+ |V2|. The assumption γCvR(G) = γcon(G)+1 forces the equality |V1| + |V2| = |V1| + 2|V2|. Hence, |V2| = 0, |V0| = 0, and |V1| = n. Consequently, γcon(G) = n − 1. Let D = V (G) \ {w} be a γcon-set in G and set S = {w}. Since D is a dominating set and G is non-trivial, there exists v ∈ D such that S ⊆ NG(v). In either case, the desired properties hold. For the converse, suppose that there exist a vertex v and a set S ⊆ V (G) such that S ⊆ NG(v) and V (G) \ S is a γcon-set in G. Let V2 = {v}, V1 = V (G) \ (S ∪ V2), and V0 = V (G) \ (V1 ∪ V2) = S. Then, by assumption, V (G) \ S = V1 ∪ V2 is convex and V0 ⊆ NG(v). Therefore, g = (V0, V1, V2) is CvRDF on G and γCvR(G) ≤ wCvR G (g) = |V1|+ 2|V2| = [n− (n− γcon(G) + 1)] + 2 R. Fortosa, S. Canoy Jr. / Eur. J. Pure Appl. Math, 16 (3) (2023), 1705-1716 1714 = γcon(G) + 1. Since γcon(G) < γCvR(G), γcon(G)+1 ≤ γCvR(G). Therefore, γCvR(G) = γcon(G)+1. Graphs G such that γCvR(G) = 2γcon(G) are called convex Roman graphs. Theorem 6. Let G be a nontrivial connected graph. The following statements are equiv- alent. (i) G is a convex Roman graph. (ii) G has a γCvR-function f = (V0, V1, V2) such that |V1| = 0. (iii) G has a γCvR-function f = (V0, V1, V2) such that V2 is a γcon-set in G. Proof. Let G be a convex Roman graph and let f = (V0, V1, V2) be a γCvR-function on G. Then 2γcon(G) = 2|V1| + 2|V2| = |V1| + 2|V2| = γCvR(G). This implies that |V1| = 0. Hence (i) implies (ii). Next, let f = (V0, V1, V2) be a γCvR-function on G with |V1| = 0. By Proposition 3(iii), V2 is a γcon-set in G and γCvR(G) = 2|V2| = 2γcon(G). Thus (ii) implies (i). The equivalence of statements (ii) and (iii) follows from Proposition 3(iii). Corollary 8. Let G be a nontrivial connected graph. If γ(G) = 1, then G is a convex Roman graph. Theorem 7. Let G and H be any connected graphs. Then γCvR(G+H) = { 2 if γ(G) = 1 or γ(H) = 1 4 otherwise. Proof. Since G+H ̸= K1, γCvR(G+H) ≥ 2, by Theorem 3(i). Suppose γ(G) = 1 or γ(H) = 1. Then γ(G+H) = 1. By Corollary 4, γCvR(G+H) = 2. Suppose γ(G) ̸= 1 and γ(H) ̸= 1. By Proposition 2, γCvR(G +H) ≥ 4. Pick any x ∈ V (G) and y ∈ V (H). Let V2 = {x, y}, V0 = V (G) \ V2, and V1 = ∅. Then f = (V0, V1, V2) is a CvRDF on G +H and ωCvR G+H(f) = 4. Therefore, γCvR(G+H) = 4. This proves the assertion. 4. Conclusion The concept of convex Roman domination was introduced and initially investigated in this study. The convex Roman domination numbers of some graphs and the join of two graphs were determined. It was shown that every pair of positive integers (with some restrictions) are realizable as the connected Roman domination number and convex Roman domination number of some connected graph. A realization result involving con- vex domination number and convex Roman domination number was also obtained. The newly defined variant of Roman domination in this study can be studied for other graphs including those ones under some binary operations. REFERENCES 1715 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. The authors are also grateful to 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] M. Adabi, E. Ebrahimi Targhi, N. Jafari Rad, and M. Saied Moradi. Properties of independent Roman domination in graphs. Australasian Journal of Combinatorics, 52:11–18, 2012. [2] H.A. Ahangar, M.A. Henning, V. Samodivkin, and I.G. Yero. Total Roman domina- tion in graphs. Applicable Analysis and Discrete Mathematics, 10(2):501–517, 2016. [3] M.P. Alvarez-Ruiz, T. Mediavilla-Gradolph, S.M. Sheikholeslami, J.C. Valenzuela- Tripodoro, and I.G. Yero. On the strong Roman domination number of graphs. Discrete Applied Mathematics, 231:44–59, 2017. [4] S. Banerjee, J.M. Keil, and D. Pradhan. Perfect Roman domination in graphs. The- oretical Computer Science, 796:1–21, 2019. [5] R.A. Beeler, T.W. Haynes, and S.T. Hedetnieme. Double Roman domination. Dis- crete Applied Mathematics, 211:23–29, 2016. [6] F. Buckey and F. Harary. Distance in Graphs. Addison-Wesley, Redwood City, California, 1990. [7] S.R. Canoy. A short note on convexity and convex domination in G[Km]. Applied Mathematical Sciences, 8(115):5737–5741, 2014. [8] S.R. Canoy and I.J.L. Garces. Convex sets under some graph operations. Graphs and Combinatorics, 18(4):787–793, 2002. [9] G. Chartrand, J. Fink, and P. Zhang. Convexity in graphs. Discrete Applied Mathe- matics, (116):115–126, 2002. [10] M. Chellali, T.W. Haynes, and S.T. Hedetnieme. Roman {2} domination. Discrete Applied Math, 204:22–28, 2016. [11] E.J. Cockayne, P.A. Deryer, S.M. Hedetnieme, and S.T. Hedetnieme. Roman Domi- nation in Graphs. Discrete Mathematics, 278(13):11–22, 2004. [12] E.L. Enriquez and S.R. Canoy. On a variant of convex domination in a graph. Inter- national Journal of Mathematical Analysis, 9(32):1585–1592, 2015. REFERENCES 1716 [13] M.A. Henning, W.F. Klostermeyer, and G. MacGillivray. Perfect Roman domination in trees. Discrete Applied Mathematics, 236:235–245, 2018. [14] K. Kammerling and L. Volkman. Roman k-domination in graphs. Journal of the Korean Mathematical Society, 46(6):1309–1318, 2009. [15] M.A. Labendia and S.R. Canoy. Convex Dominatioin in the composition and Carte- sian product of graphs. Czechoslovak Mathematical Journal, 62:1003–1009, 2012. [16] M. Lemanska. Weakly convex and convex domination numbers. Opuscula Mathemat- ica, 24(2):181–188, 2004. [17] M.H. Muddebiha and Sumangaladevi. Connected Roman domination in graphs. In- ternational Journal of Research and Engineering Technology, 2(10):333–340, 2013. [18] P.R.L. Pushpam and T.N.M. Malini Mai. Edge Roman domination in graphs. Journal of Combinatorial Mathematics and Combinatorial Computing, 69:175–182, 2009. [19] J. Cyman snd M. Lemańska and J. Raczek. Graphs with convex domination number close to their order. Discussiones Mathematicae Graph Theory, 26(2):307–316, 2006.