EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS
Vol. 17, No. 2, 2024, 1335-1351
ISSN 1307-5543 – ejpam.com
Published by New York Business Global

Convex Roman Dominating Functions on Graphs under
some Binary Operations

Rona Jane G. Fortosa1,∗, Ferdinand P. Jamil1,2, 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
2 Center of 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 specifically study the concept of convex Roman domination in the corona and edge
corona of graphs, complementary prism, lexicographic product, and Cartesian product of graphs.

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, corona, edge corona,
complementary prism, lexicographic product, Cartesian product

1. Introduction

Roman domination was first introduced by Cockayne, Dreyer and Hedetnieme in [8]
which was inspired by the defense strategy of the Roman emperor Constantine the Great
during the 4th Century AD (see [23] and [24]). After several years, lots of variations on
this concept have been introduced and studied (see [1], [2], [3], [4], [5], [7], [13], [16], [19],
[20], and [22]).

The concept of convex domination in graphs was first introduced by Lemanska in
2004 [18]. Convex domination is a concept in graph theory that combines the notions of
convexity and domination. Studies related on convexity and dominaton in graphs can be
found in [14], [15], [6], [9], [11], [12], and [21]. A subset of vertices in a graph is said to
be a convex dominating set if it is both a convex set and a dominating set, which means

∗Corresponding author.
DOI: https://doi.org/10.29020/nybg.ejpam.v17i2.5205

Email addresses: ronajane.fortosa@g.msuiit.edu.ph (R.J. Fortosa),
sergio.canoy@g.msuiit.edu.ph (S. Canoy), ferdinand.jamil@g.msuiit.edu.ph (F. Jamil)

https://www.ejpam.com 1335 © 2024 EJPAM All rights reserved.



R. Fortosa, S. Canoy Jr. / Eur. J. Pure Appl. Math, 17 (2) (2024), 1335-1351 1336

that every vertex on the shortest path between any two vertices in the set is also in the
set and every vertex in the graph is either in the set or adjacent to a vertex in the set.

The convex Roman domination was introduced and initially investigated in [10] where
properties of convex Roman dominating functions and convex Roman domination number
of some graphs and the join of two graphs have been obtained.

In this present paper, authors continued the study of convex Roman domination, specif-
ically on the corona, edge corona, complementary prism, lexicographic product, and Carte-
sian product of graphs.

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 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.

If S is a clique (the induced graph ⟨S⟩ is complete) and a dominating set, then S
is called a clique dominating set in G. A clique domination number γcl(G) of G is the
smallest cardinality of a clique dominating set in 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. Any convex dominating set S of G with |S| = γcon(G)
is called a γcon-set 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 on G. Any
RDF f on G with ωG(f) = γR(G) is called a γR-function. If f is an RDF on G and
Vi = {v ∈ V (G) : f(v) = i} for i ∈ {0, 1, 2}, then we denote f by f = (V0, V1, V2). In this
case, ωG(f) = |V1|+ 2|V2|.

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) on G is given by ωCvR

G (f) = |V1| + 2|V2|. The minimum weight



R. Fortosa, S. Canoy Jr. / Eur. J. Pure Appl. Math, 17 (2) (2024), 1335-1351 1337

of a CvRDF on G, denoted by γCvR(G), is called the convex Roman domination number
of G. Any CvRDF f on G with ωCvR

G (f) = γCvR(G) is called a γCvR-function.

2. Known Results

The following results are useful in this study.

Proposition 1. [10] Let n be a positive integer. Then

γCvR(Pn) =


1, n = 1

2, n = 2, 3

n, n ≥ 4.

Proposition 2. [10] Let G be a non-trivial 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

Theorem 1. [15] Let G be a connected graph and Km the complete graph of order m.
Then a proper subset C = S1 ∪ S2 of V (G+Km), where S1 ⊆ V (G) and S2 ⊆ V (Km), is
convex in G+Km if and only if either

(i) S1 induces a complete subgraph of G, or

(ii) S1 = V (G) \ S and S2 = V (Km) for some non-connecting set S in G.

Theorem 2. [14] Let G be a connected graph and Km the complete graph of order n ≥ 2.
A subset C =

⋃
x∈S({x}×Tx), where S ⊆ V (G) and Tx ⊆ V (H), is a convex set in G[Km]

if and only if S is a convex set in G and Tx = V (Km) for each x ∈ S0 = I(S) ∩ S.

Theorem 3. [15] Let G and H be connected non-complete graphs. A subset C =⋃
x∈S({x} × Tx) of V (G[H]) is a convex set in G[H] if and only if S is a clique set

in G and Tx is a clique in H for each x ∈ S.

Theorem 4. [17] Let G and H be connected non-complete graphs. A subset C =
⋃

x∈S({x}×
Tx) of V (G[H]) is a convex dominating set in G[H] if and only if S is a clique dominating
set in G and Tx is a clique in H for each x ∈ S.

Theorem 5. [15] Let G and H be two connected graphs. A set C ∈ V (G□H) is a convex
set in G□H if and only if C = CG × CH , where CG and CH are convex sets in G and H
respectively.

Theorem 6. [17] Let G and H be connected graphs. A subset C of V (G□H) is a convex
dominating set in G□H if and only if C = C1 × C2 and one of the following conditions
holds:



R. Fortosa, S. Canoy Jr. / Eur. J. Pure Appl. Math, 17 (2) (2024), 1335-1351 1338

(i) C1 is a convex dominating set in G and C2 = V (H), or

(ii) C2 is a convex dominating set in H and C1 = V (G).

Theorem 7. [10] 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 = K2 or G = K1 +H for some graph H

Corollary 1. [10] For any connected graph G of order n, γCvR(G) = 2 if and only if
G ̸= K1 and γ(G) = 1.

Proposition 3. [10] There exists no connected graph G with γCvR(G) = 3.

Proposition 4. [10] For any connected graph G of order n,

1 ≤ γcon(G) ≤ γCvR(G) ≤ min{n, 2γcon(G)}.

3. Results

Let G and H be connected graphs. 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 vertices 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⟩.

Let G be a graph. A non-empty subset S of V (G) is a non-connecting set in G
if it satisfies the following condition: For every pair of vertices u, v ∈ V (G) \ S with
dG(u, v) = 2, we have NG(u) ∩ NG(v) ∩ S = ∅. A non-connecting set with minimum
cardinality is called a minimum non-connecting set.

Let f = (V0, V1, V2) be a CvRDF on G ◦H. For each v ∈ V (G), let Sv
k = Vk ∩ V (Hv)

where k = 0, 1, 2.

Theorem 8. Let G be a non-trivial connected graph and let H be any graphs. Then
f = (V0, V1, V2) is a CvRDF on G ◦H if and only if each of the following conditions hold:

(i) V0 ∩ V (G) = ∅

(ii) For each v ∈ V2 ∩ V (G), Sv
1 ∪ Sv

2 induces a complete subgraph of Hv or
V (Hv) \ (Sv

1 ∪ Sv
2 ) is a non-connecting set in Hv.

(iii) For each v ∈ V1∩V (G) such that Sv
1 ̸= V (Hv), Sv

2 ̸= ∅, Sv
0 ⊆ NHv(Sv

2 ), and Sv
1 ∪Sv

2

induces a complete subgraph of Hv or V (Hv) \ (Sv
1 ∪ Sv

2 ) is a non-connecting set in
Hv and

Proof. Let f = (V0, V1, V2) be a CvRDF of G ◦ H. Since V1 ∪ V2 is a dominating set of
G ◦H,

V (v +Hv) ∩ (V1 ∪ V2) ̸= ∅ (1)



R. Fortosa, S. Canoy Jr. / Eur. J. Pure Appl. Math, 17 (2) (2024), 1335-1351 1339

for each v ∈ V (G). Suppose that there exists v ∈ V0 ∩ V (G). Then (1) implies that
Sv
1 ∪ Sv

2 ̸= ∅. Pick w ∈ V (G) \ {v}. If w ∈ V1 ∪ V2, then the convexity of V1 ∪ V2 implies
that v ∈ IG◦H [z, w] ⊆ V1 ∪ V2 for all z ∈ Sv

1 ∪ Sv
2 . Suppose that w ∈ V0. Then by (1),

Sw
1 ∪ Sw

2 ̸= ∅, and w, v ∈ IG◦H [a, b] ⊆ V1 ∪ V2, for all a ∈ Sv
1 ∪ Sv

2 and b ∈ Sw
1 ∪ Sw

2 . In
any case, we get a contradiction. Thus, V0 ∩ V (G) = ∅, showing that (i) holds.

Next, let v ∈ V2 ∩ V (G). By Theorem 1, convexity of V1 ∪ V2 implies that Sv
1 ∪ Sv

2

induces a complete subgraph of Hv or V (Hv) \ (Sv
1 ∪ Sv

2 ) is a non-connecting set in Hv.
Hence, (ii) holds. Suppose v ∈ V1 ∩ V (G) such that Sv

1 ̸= V (Hv). Then Sv
2 ̸= ∅ and

Sv
0 ⊆ NHv(Sv

2 ) because f is an RDF on G ◦ H. Again, by Theorem 1, Sv
1 ∪ Sv

2 induces
a complete subgraph of Hv or V (Hv) \ (Sv

1 ∪ Sv
2 ) is a non-connecting set in Hv, showing

that (iii) holds.
Conversely, suppose that (i), (ii) and (iii) hold. Let x ∈ V0. By (i), x ∈ Sv

0 for
some v ∈ V (G). If v ∈ V2, then x ∈ NG◦H(v). Suppose v ∈ V1. By (iii), Sv

2 ̸= ∅ and
x ∈ NG◦H(Sv

2 ). Thus f = (V0, V1, V2) is an RDF on G ◦H. Now, let p, q ∈ V1 ∪ V2 and let
v, w ∈ V (G) such that p ∈ V (v +Hv) and q ∈ V (w +Hw). Consider the following cases.
Case 1. v = w.
If p = v or q = v, then IG◦H [p, q] = {p, q} ⊆ V1 ∪ V2. Suppose p, q ∈ V (Hv). If
dHv(p, q) = 1, then IG◦H [p, q] = {p, q} ⊆ V1 ∪ V2. If dHv(p, q) = 2, then

IG◦H [p, q] = {p, q, v} ∪ (NHv(p) ∩NHv(q)) ⊆ Sv
1 ∪ Sv

2 ∪ {v} ⊆ V1 ∪ V2

since V (Hv) \ (Sv
1 ∪Sv

2 ) is a non-connecting set in Hv (by (ii) and (iii)). If dHv(p, q) > 2,
then IG◦H [p, q] = {p, q, v} ⊆ V1 ∪ V2.

Case 2. v ̸= w.
Consider the following subcases.
Subcase 1. p = v and q = w.
Then V (G) ⊆ V1 ∪ V2 by (i). Since every p-q geodesic in G ◦H is a p-q geodesic in G, it
follows that IG◦H [p, q] = IG[p, q] ⊆ (V1 ∪ V2).

Subcase 2. p = v and q ∈ V (Hw) (or q = w and p ∈ V (Hv)).
Then IG◦H [p, q] = IG[v, w] ∪ {q} ⊆ (V1 ∪ V2).

Subcase 3. p ∈ V (Hv) and q ∈ V (Hw).
Then IG◦H [p, q] = IG[v, w] ∪ {p, q} ⊆ V1 ∪ V2.

Therefore, V1 ∪ V2 is a convex set in G ◦H. Accordingly, f is a CvRDF on G ◦H.

Corollary 2. Let G be a non-trivial connected graph of order n and let H be any graph.
Then

γCvR(G ◦H) = 2n.

Proof. Let V ′
2 = V (G), V ′

0 =
⋃

v∈V (G) V (Hv), and V ′
1 = ∅. By Theorem 8,

g = (V ′
0 , V

′
1 , V

′
2) is a CvRDF on G◦H. Thus, γCvR(G◦H) ≤ ωCvR

G◦H(g) = |V ′
1 |+2|V ′

2 | = 2n.
Next, let f = (V0, V1, V2) be a γCvR-function on G ◦ H. Let V ∗

1 = V1 ∩ V (G) and
V ∗
2 = V2 ∩ V (G) and let |V ∗

1 | = k. Then |V ∗
2 | = n− k. Let D = {v ∈ V ∗

1 : Sv
1 ̸= ∅}. Then

Sv
2 ̸= ∅ for all v ∈ V1 \D by (iii). Hence,

γCvR(G ◦H) = ωCvR
G◦H(f)



R. Fortosa, S. Canoy Jr. / Eur. J. Pure Appl. Math, 17 (2) (2024), 1335-1351 1340

= |V1|+ 2|V2|

= k +
∑

v∈V (G)

|Sv
1 |+ 2

(n− k) +
∑

v∈V (G)

|Sv
2 |


= 2n− k +

∑
v∈V (G)

|Sv
1 |+ 2

∑
v∈V (G)

|Sv
2 |

≥ 2n− k +
∑
v∈D

|Sv
1 |+ 2

∑
v∈V1\D

|Sv
2 |

≥ 2n− k + |D|+ 2|V1| − 2|D|
= 2n+ k − |D|
≥ 2n.

This proves the desired equality.

Given graphs G and H we write Huv to denote that copy of H that is being joined
with the end vertices of the edge uv ∈ E(G) in the edge corona G ⋄H. If H = {x}, then
we write V (Huv) = {xuv}.

Recall that for subsets A and B of V (G), we have dG(A,B) = min{dG(a, b) : a ∈
A and b ∈ B}.

Let f = (V0, V1, V2) be a CvRDF on G⋄H. For each v ∈ V (G), let Suv
1 = V1∩V (Huv)

and Suv
2 = V2 ∩ V (Huv). Denote V 0

G = V (G) ∩ V0, V
1
G = V (G) ∩ V1, and V 2

G = V (G) ∩ V2.

Note that since γ(K2 ⋄ H) = 1 for any graph H, it follows from Corollary 1 that
γCvR(K2 ⋄H) = 2.

Theorem 9. Let G be a non-trivial connected graph such that G ̸= K2 and let H be any
graph. Then f = (V0, V1, V2) is a CvRDF on G ⋄ H if and only if each of the following
conditions holds.

(i) |{u, v} ∩ (V 1
G ∪ V 2

G)| ≠ 0 for each uv ∈ E(G).

(ii) For each pair of distinct edges uv and zw of G, IG(x, y) ⊆ V 1
G ∪ V 2

G whenever
x ∈ {u, v} ∩ (V 1

G ∪ V 2
G) and y ∈ {z, w} ∩ (V 1

G ∪ V 2
G).

(iii) For every pair of distinct edges e and e′ of G with Se
1 ∪ Se

2 ̸= ∅ and Se′
1 ∪ Se′

2 ̸= ∅,
v, z ∈ V 1

G ∪ V 2
G whenever v and z are incident with e and e′, respectively, with

dG(v, z) = dG({u, v}, {z, w}).

(iv) For each uv ∈ E(G) such that {u, v} ∩ (V1 ∪ V2) = {v}, it holds that

(a) Suv
1 ∪ Suv

2 a clique in Huv whenever Suv
1 ∪ Suv

2 ̸= ∅ and

(b) v ∈ V 2
G or Suv

2 ̸= ∅ and Suv
0 ⊆ NHuv(Suv

2 ).

(v) For each uv ∈ E(G) such that {u, v} ⊆ (V1 ∪ V2) and Suv
1 ∪ Suv

2 ̸= V (Huv), it holds
that



R. Fortosa, S. Canoy Jr. / Eur. J. Pure Appl. Math, 17 (2) (2024), 1335-1351 1341

(c) V (Huv) \ (Suv
1 ∪ Suv

2 ) is a non-connecting set in Huv and

(d) {u, v} ∩ V 2
G ̸= ∅ or Suv

2 ̸= ∅ and Suv
0 ⊆ NHuv(Suv

2 ).

Proof. Let u, v ∈ V (G) such that uv ∈ E(G). Then |{u, v}∩(V 1
G∪V 2

G)| ≠ 0 because V1∪V2

is convex in G ⋄H and G ̸= K2. Thus, (i) holds.
Let uv and zw be distinct edges of G and let x ∈ {u, v} ∩ (V 1

G ∪ V 2
G) and

y ∈ {z, w} ∩ (V 1
G ∪ V 2

G). Since V1 ∪ V2 is convex in G ⋄ H, it follows that
IG(x, y) = IG⋄H(x, y) ⊆ V1 ∪ V2. Therefore, IG(x, y) ⊆ V 1

G ∪ V 2
G, showing that (ii) holds.

Let e and e′ be distinct edges of G with Se
1 ∪ Se

2 ̸= ∅ and Se′
1 ∪ Se′

2 ̸= ∅ and suppose
that v and z are incident with e and e′, respectively, with dG(v, z) = dG({u, v}, {z, w}).
Let x ∈ Se

1 ∪ Se
2 and y ∈ Se′

1 ∪ Se′
2 . Then IG[v, z] ⊆ IG⋄H [x, y]. Since V1 ∪ V2 is convex,

IG⋄H [x, y] ⊆ V1 ∪ V2. Hence, v, z ∈ V 1
G ∪ V 2

G. This shows that (iii) holds.
Now, let uv ∈ E(G) such that {u, v} ∩ (V1 ∪ V2) = {v}. Since V1 ∪ V2 is convex, (a)

holds. Also, (b) holds since f is a CvRDF on G ⋄H. Thus, (iv) holds.
Next, let uv ∈ E(G) such that {u, v} ⊆ (V1 ∪ V2) and Suv

1 ∪ Suv
2 ̸= V (Huv). By

Theorem 1, (c) holds. Since f is CvRDF on G ⋄H, (d) also holds. Hence, (v) holds.
Conversely, assume that (i), (ii), (iii), and (iv) hold. Let x ∈ V0 and let uv ∈ E(G)

such that x ∈ V ({u, v}+Huv). Consider the following cases:

Case 1. Suppose that x ∈ V 0
G, say x = u.

Suppose v /∈ V 2
G. Then Suv

2 ̸= ∅ by (iv)(b). Let p ∈ Suv
2 . Then p ∈ V2 ∩NG⋄H(u).

Case 2. Suppose that x ∈ Suv
0 .

If u ∈ V2 or v ∈ V2, then xu ∈ E(G ⋄H) or xv ∈ E(G ⋄H). Suppose u, v /∈ V2. Then, by
(iv)(b), there exists q ∈ Suv

2 ∩NHuv(x). Hence, q ∈ V2 ∩NG⋄H(x).

Thus, by Case 1 and Case 2, f = (V0, V1, V2) is an RDF on G ⋄H.
Next, let x, y ∈ V1 ∪V2 (x ̸= y) and uv, zw ∈ E(G) such that x ∈ V ({u, v}+Huv) and

y ∈ V ({z, w}+Hzw). Consider the following cases:

Case 1. uv = zw.
If x = u and y = v, then IG⋄H [x, y] = {x, y} ⊆ V1 ∪ V2. Suppose that x, y ∈ Suv

1 ∪
Suv
2 . If |{u, v} ∩ (V1 ∪ V2)| = 1, then Suv

1 ∪ Suv
2 induces a complete subgraph of Huv

by (iv)(a). Therefore, IG⋄H [x, y] = {x, y} ⊆ V1 ∪ V2. Suppose that |{u, v} ∩ (V1 ∪
V2)| = 2. Clearly, IG⋄H [x, y] ⊆ V1 ∪ V2 if Suv

1 ∪ Suv
2 = V (Huv). Suppose Suv

1 ∪ Suv
2 ̸=

V (Huv). Then V (Huv) \ Suv
1 ∪ Suv

2 is a non-connecting set in Huv by (v)(c). Hence,
NHuv(x) ∩NHuv(y) ⊆ Suv

1 ∪ Suv
2 . Therefore, IG⋄H [x, y] ⊆ V1 ∪ V2.

Case 2. uv ̸= zw.
Suppose that x ∈ {u, v} and y ∈ {z, w}. By (ii), IG⋄H [x, y] = IG[x, y] ⊆ V 1

G∪V 2
G. Suppose

that x ∈ Suv
1 ∪Suv

2 and y ∈ Szw
1 ∪Szw

2 . Suppose uv and zw are adjacent, say v = z. Then
v ∈ V 1

G ∪ V 2
G by (iii). Hence, IG⋄H [x, y] = {x, v, y} ⊆ V1 ∪ V2. Next, suppose that uv and

zw are non-adjacent. Let a and b be incident with e = uv and e′ = zw, respectively, with
dG(a, b) = dG({u, v}, {z, w}). Then a, b ∈ V 1

G ∪V 2
G, by (iii). Moreover, IG[a, b] ⊆ V 1

G ∪V 2
G,

by (ii). Therefore, IG⋄H(x, y) = IG[a, b] ⊆ V1 ∪ V2. Finally, suppose that x ∈ Suv
1 ∪ Suv

2

and y ∈ {z, w}. Suppose that a and b are the vertices described earlier. If b = y, then



R. Fortosa, S. Canoy Jr. / Eur. J. Pure Appl. Math, 17 (2) (2024), 1335-1351 1342

IG⋄H(x, y) = IG(a, b)∪{a} ⊆ V1∪V2, by (ii). Again, by (ii), IG⋄H(x, y) = IG[a, b] ⊆ V1∪V2

if b ̸= y.
Therefore, V1 ∪ V2 is convex in G ⋄H. Accordingly, f is a CvRDF on G ⋄H.

Lemma 1. Let G be a non-complete connected graph and H be any graph of order n. If
W0 = Ext(G), W1 ∪W2 = V (G) \Ext(G) and {u, v} ∩W2 ̸= ∅ for each uv ∈ E(G) such
that |{u, v} ∩ Ext(G)| ≠ 2, then f |G = (W0,W1,W2) is a CvRDF on G.

Proof. Let x ∈ W0. Since G is non-complete, there exists y ∈ (V (G) \ Ext(G)) ∩NG(x).
By assumption, this implies that y ∈ W2, showing that f is an RDF on G. Moreover,
since V (G) \ Ext(G) is convex in G, it follows that f is a CvRDF on G.

Henceforth, we refer f in Lemma 1 as a CvRDF* on G.

Corollary 3. Let G be a non-complete connected graph and H any graph of order n. Then

γCvR(G ⋄H) ≤ min{ωCvR
G (f) : f = (W0,W1,W2) is a CvRDF ∗ on G}.

Proof. Let k = min{ωCvR
G (f) : f = (W0,W1,W2) is a CvRDF ∗ on G}. Let

g = (W0,W1,W2) be a CvRDF* on G such that ωCvR
G (g) = k. Let

V0 = Ext(G) ∪ (
⋃

e∈E(G) V (He)), V1 = W1, V2 = W2, and let h = (V0, V1, V2). Clearly,
h|G = g. Hence, h satisfies (i). Also, (ii), (iii) and (iv) of Theorem 9 hold. Thus, by
Theorem 9, h is a CvRDF on G ⋄H. Moreover,

γCvR(G ⋄H) ≤ ωG⋄H(h) = |V1|+ 2|V2| = |W1|+ 2|W2| = γ∗CvR(G).

Remark 1. The bound given in Corollary 3 is sharp. It can be verified that for any graph
H and positive integer n ≥ 3, the following holds:

γCvR(Pn ⋄H) = min{ωCvR
Pn

(f) : f is a CvRDF ∗ on Pn}

=

{
3n−4

2 , if n is even
3n−5

2 , if n is odd.

For a graph G, the complementary prism, denoted GG, is formed from the disjoint
union of G and its complement G by adding a perfect matching between corresponding
vertices of G and G. For each v ∈ V (G), let v denote the vertex corresponding to v in G.
Formally, the graph GG is formed from G∪G by adding the edge vv for every v ∈ V (G).

Proposition 5. Let G be a graph on n vertices. Then each of the following holds.
(i) γCvR(GG) = 2 if and only if G = K1.
(i) γCvR(GG) = 4 if and only if G = K2 or K2.

Proof. (i) Suppose that G = K1. Then GG = K2. By Theorem 7, we are done.

(ii) Suppose that G = K2 or G = K2. Then G = P4 and by Theorem 1,
γCvR(GG) = γCvR(P4) = 4. Conversely, suppose that γCvR(GG) = 4. Let
f = (V0, V1, V2) be a γCvR-function. Then ωCvR

GG
(f) = |V1| + 2|V2| = 4. Then |V2| ≤ 2. If



R. Fortosa, S. Canoy Jr. / Eur. J. Pure Appl. Math, 17 (2) (2024), 1335-1351 1343

|V2| = 0, then V1 = V (GG). Hence, GG = P4. This implies that G ∈ {K2,K2}. Suppose
that |V2| = 1, say V2 = {u}. Then |V1| = 2. WLOG, asssume that u ∈ V (G). Suppose
|V (G)| ≥ 3 and let v, w ∈ V (G) \ {u}. Since v, w /∈ NGG(u), V1 = {v, w}. Because V1 ∪V2

is convex, one of the following holds:

u ∈ IGG[u, z] ⊆ V1 ∪ V2, where z ∈ {v, w},
v ∈ IGG[u, z] ⊆ V1 ∪ V2, where z ∈ {v, w},
w ∈ IGG[u, z] ⊆ V1 ∪ V2, where z ∈ {v, w}.

In any case, we have a contradiction. Thus, |V (G)| ≤ 2. But by statement (i),
|V (G)| = 2. This means that G ∈ {K2,K2}. If |V2| = 2, then |V1| = 0. By Proposi-
tion 2, V2 is a γcon-set in GG. Let V2 = {x, y}. WLOG, assume that x ∈ V (G). If x = y,
then NG[x] = V (G) and NG[y] = V (G). This is possible only if G = K1, a contradiction.
Thus y ∈ V (G) and xy ∈ E(G). Now, for each z ∈ V0 = V (G) \ {x, y}, xz /∈ E(GG) and
yz /∈ E(GG). Hence, V (G) \ {x, y} = ∅. Therefore, G ∈ {K2,K2}.

Proposition 6. For any connected graph G of order n,

2 ≤ γCvR(GG) ≤ 2min{γcon(GG), n}.

In particular,

(i) γCvR(GG) = 2γcon(GG) if there exists a γCvR-function f = (V0, V1, V2) with V1 = ∅.

(ii) If G = Kn, then γCvR(GG) = 2n.

Proof. By Proposition 4, γCvR(GG) ≤ 2γcon(GG). Define f = (V0, V1, V2), where
V2 = V (G), V1 = ∅, and V0 = V (G). Then f is a CvRDF of GG. Thus
γCvR(GG) ≤ 2|V2| = 2n.

It is worth noting that if G = P4, γcon(GG) = 8 > 4. If G = P5, γcon(GG) = 4 < 5.

The lexicographic product of two 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).

For S ⊆ V (G[H]), we write

SG = {x ∈ V (G) : (x, a) ∈ S for some a ∈ V (H)}.

SG is referred to as the G-projection of S in G[H].
Let f = (V0, V1, V2) be a CvRDF on G[H]. We write

S0
G = {x ∈ V (G) : (x, a) ∈ V0 for some a ∈ V (H)},

S1
G = {x ∈ V (G) : (x, a) ∈ V1 for some a ∈ V (H)},

S2
G = {x ∈ V (G) : (x, a) ∈ V2 for some a ∈ V (H)},

V 0
G = S0

G \ (S1
G ∪ S2

G),



R. Fortosa, S. Canoy Jr. / Eur. J. Pure Appl. Math, 17 (2) (2024), 1335-1351 1344

V 1
G = S1

G \ (S0
G ∪ S2

G),

V 2
G = V (G) \ (V 0

G ∪ V 1
G), and

S0
f = I(S1

G ∪ S2
G) ∩ (S1

G ∪ S2
G).

Note that if V 1
G ̸= V (G), then V 2

G ̸= ∅ because f is a Roman dominating function on
G[H].

Theorem 10. Let G be a non-trivial connected graph and Km a complete graph. Then
f = (V0, V1, V2) is a CvRDF on G[Km] if and only if each of the following conditions hold:

(i) g|f = (V 0
G, V

1
G, V

2
G) is a CvRDF on G.

(ii) S1
G ∪ S2

G is convex in G.

(iii) {x} × V (Km) ⊆ V1 ∪ V2 for x ∈ S0
f .

(iv) For each v ∈ (S0
G \ S2

G) ∩ S1
G, there exists w ∈ S2

G ∩NG(v).

Proof. Let f = (V0, V1, V2) be a CvRDF on G[Km]. Consider the function
gf = (V 0

G, V
1
G, V

2
G) on G. Let x ∈ V 0

G and let q ∈ V (Km). Then (x, q) ∈ V0. Since f
is a CvRDF on G[Km], there exists (y, t) ∈ V2 such that (x, q)(y, t) ∈ E(G[Km]). This
implies that xy ∈ E(G) and y ∈ V 2

G. Thus, g|f is an RDF on G. Let u, v ∈ V 1
G ∪ V 2

G such
that u ̸= v. Let x ∈ IG(u, v). Let P (u, v) = [u, u1, u2, . . . , uk, v] be a u-v geodesic in G
with x = ur for some 1 ≤ r ≤ k. Consider the following cases:

Case 1. u, v ∈ V 1
G (or u, v ∈ V 2

G)
Pick any t ∈ V (Km). Then (u, t) ∈ V1. Then
P ((u, t), (v, t) = [(u, t), (u1, t), . . . , (ur−1, t), (ur, t), . . . , (uk, t), (v, t)] is a (u, t)-(v, t) geodesic
in G[Km]. Since V1 ∪ V2 is a convex set in G[Km], it follows that (ur, t) ∈ V1 ∪ V2. This
implies that x = ur ∈ V 1

G ∪ V 2
G. A similar argument is used to show that x ∈ V 1

G ∪ V 2
G

whenever u, v ∈ V 2
G.

Case 2. u ∈ V 1
G and v ∈ V 2

G

Pick any s ∈ V (Km) such that (v, s) ∈ V2. Then (u, s) ∈ V1 and
P ((u, s), (v, s)) = [(u, s), (u1, s), . . . , (ur−1, s), (ur, s), . . . , (uk, s), (v, s)] is a (u, s)-(v, s)
geodesic in G[Km]. Since V1∪V2 is a convex set in G[Km], it follows that (ur, s) ∈ V1∪V2.
This implies that x = ur ∈ V 1

G ∪ V 2
G.

Therefore, g is a CvRDF on G, showing that (i) holds.
Let x, y ∈ S1

G ∪ S2
G with x ̸= y and let z ∈ IG(x, y). Let P (x, y) = [x, x1, x2, . . . , xk, y]

be an x-y geodesic in G where z = xj for some 1 ≤ j ≤ k. Let a, b ∈ V (Km) such that
(x, a), (y, b) ∈ V1 ∪ V2. Then P ((x, a), (y, b)) = [(x, a), (x1, a), (x2, a), . . . , (xk, a), (y, b)] is
an (x, a)-(y, b) geodesic in G[Km]. Since V1∪V2 is a convex set in G[Km], (xj , a) ∈ V1∪V2.
Hence, xj ∈ S1

G ∪ S2
G. This shows that S

1
G ∪ S2

G is convex in G, i.e., (ii) holds.
Next, let x ∈ S0

f and let p ∈ V (Km). Then x ∈ S1
G∪S2

G and there exists y, z ∈ S1
G∪S2

G

such that x ∈ IG(y, z). Again, by convexity of V1 ∪ V2, (x, p) ∈ V1 ∪ V2. This shows that
(iii) holds.



R. Fortosa, S. Canoy Jr. / Eur. J. Pure Appl. Math, 17 (2) (2024), 1335-1351 1345

Finally, let v ∈ (S0
G \ S2

G) ∩ S1
G and let a ∈ V (Km) such that (v, a) ∈ V0. Since f is

a CvRDF on G[Km], there exists (w, b) ∈ V2 such that (v, a)(w, b) ∈ E(G[Km]). Hence,
w ∈ S2

G and v ∈ NG(w). Hence, (iv) holds.
Conversely, assume that (i), (ii), (iii), and (iv) hold. Let (v, p) ∈ V0. Then v ∈ S0

G.
If v ∈ S2

G, then (v, q) ∈ V2 for some q ∈ V (Km) and (v, p)(v, q) ∈ E(G[Km]). Suppose
v /∈ S2

G. Suppose further that v ∈ S1
G. Then by (iv), there exists w ∈ S2

G such that
v ∈ NG(w). Let c ∈ V (Km) such that (w, c) ∈ V2. Then (v, p)(w, c) ∈ E(G[H]). Next,
suppose that v /∈ S1

G∪S2
G. Then v ∈ V 0

G. By (i), there exists z ∈ V 2
G such that vz ∈ E(G).

Let d ∈ V (Km) such that (z, d) ∈ V2. Then (v, p)(z, d) ∈ E(G[Km]). Thus f is an RDF
on G[Km].

Now, let V1 ∪ V2 =
⋃

x∈S [{x} × Tx]. Then S = S1
G ∪ S2

G and Tx ⊆ V (Km) for each
x ∈ S. Morever, by (iii), Tx = V (Km) for each x ∈ IG(S) ∩ S. Thus, by Theorem 2,
V1 ∪ V2 is convex in G[Km]. Therefore, f is a CvRDF on G[Km].

Lemma 2. Let G be a non-trivial connected graph with G ̸= K2 and let m be any positive
integer. If h = (W0,W1,W2) is a CvRDF on G such that

k = ωCvR(h) + (m− 1)
∣∣S0

h

∣∣ = min
{
ωCvR
G (h′) + (m− 1)

∣∣S0
h′
∣∣} ,

then W1 ⊆ S0
h.

Proof. Suppose there exists x ∈ W1 \ S0
h. Suppose x ∈ NG(W0), say y ∈ W0 ∩ NG(x).

Since h is an RDF on G, there exists v ∈ W2 such that y ∈ NG(v). By convexity of
W1 ∪ W2, xv ∈ E(G). Let W ′

0 = W0 ∪ {x}, W ′
1 = W1 \ {x}, and W ′

2 = W2. Then
h′ = (W ′

0,W
′
1,W

′
2) is an RDF on G. Let p, q ∈ W ′

1 ∪ W ′
2 such that p ̸= q. Then

p, q ∈ W1 ∪ W2 and IG(p, q) ⊆ W1 ∪ W2 since W1 ∪ W2 is convex. Let z ∈ IG(p, q).
Since x ∈ W1 \ S0

h, x /∈ IG(W1 ∪ W2). Thus, z ̸= x. Hence, z ∈ W ′
1 ∪ W ′

2, i.e.,
IG(p, q) ⊆ W ′

1 ∪ W ′
2, showing that W ′

1 ∪ W ′
2 is convex in G. Therefore, h′ is a CvRDF

on G and ωCvR
G (h′) = |W ′

1| + 2|W ′
2| = |W1| − 1 + 2|W2| < ωCvR

G (h), a contradiction.
Thus, x /∈ NG(W0). Next, suppose x ∈ NG(W2), say {z} ∈ W2 ∩ NG(x). Following the
argument above, this is also not possible. Thus, x /∈ NG(W2). Therefore, NG(x) ⊆ W1.
Suppose that NG(x) ⊆ W1 \ S0

h. Suppose there exists y ∈ NG(x) ∩ (W1 \ S0
h). Since

|V (G)| ≥ 3, there exists z ∈ NG(x) ∪ NG(y). Moreover, since x, y /∈ S0
h,

z ∈ NG(x) ∩ NG(y). It follows that y, z ∈ W1 \ S0
h. Let W ∗

0 = W0 ∪ {x, z},
W ∗

1 = W1 \ {x, z, y}, and W ∗
2 = W2 ∪ {y}. Then h∗ = (W ∗

0 ,W
∗
1 ,W

∗
2 ) is a CvRDF on

G and ωCvR
G (h∗) < ωCvR

G (h). Since S0
h∗ ⊆ S0

h, it follows that ω
CvR
G (h∗)+ (m− 1)

∣∣S0
h∗ | < k,

a contradiction. Therefore, NG(x) ∩ (W1 ∩ S0
h) ̸= ∅. Let vx ∈ NG(x) ∩ (W1 ∩ S0

h). Let
V0 = W0∪{x}, V1 = W1\{x, vx} and V2 = W2∪{vx}. Then f = (V0, V1, V2) is a CvRDF on
G and ωCvR

G (f) = ωCvR
G (h). Since x /∈ S0

f , |S0
f | < |S0

h|. Thus, ωCvR
G (f) + (m− 1)

∣∣S0
f | < k,

a contradiction. Therefore, W1 \ S0
h = ∅, i.e, W1 ⊆ S0

h.

Corollary 4. Let G be a non-trivial connected graph and Km be a complete graph of order
m ≥ 1. Then

γCvR(G[Km]) = min
{
ωCvR
G (g) + (m− 1)

∣∣S0
g | : g is a CvRDF on G

}
.



R. Fortosa, S. Canoy Jr. / Eur. J. Pure Appl. Math, 17 (2) (2024), 1335-1351 1346

Proof. Let k = min
{
ωCvR
G (g) + (m− 1)

∣∣S0
g | : g is a CvRDF on G

}
. Let f = (V0, V1, V2)

be a γCvR-function on G[Km]. Then g = (V 0
G, V

1
G, V

2
G) is a CvRDF on G, by Theorem

10 (i). For each x ∈ S1
G, let Dx = {(x, p) ∈ V1 : p ∈ V (Km)}. For each y ∈ S2

G,
let Ry = {(y, q) ∈ V2 : q ∈ V (Km)}. Since f is a γCvR-function, S0

f ⊆ V 1
G. Hence,

S0
f ∩ S1

G = S0
f and S0

f ∩ S2
G = ∅. Consequently,

γCvR(G[Km]) = ωG[Km](f)

= |V1|+ 2|V2|
=

∑
x∈S1

G\S0
f

|Dx|+
∑
x∈S0

f

|Dx|+ 2
∑
y∈S2

G

|Ry|

≥ |S1
G \ S0

f |+m|S0
f |+ 2|S2

G|
= |S1

G|+ 2|S2
G|+ (m− 1)|S0

f |
≥ |V 1

G|+ 2|V 2
G|+ (m− 1)|S0

g |
= ωCvR(g) + (m− 1)|S0

g | ≥ k.

Let h = (W0,W1,W2) be a CvRDF on G such that
k = min{ωCvR

G (g) + (m − 1)
∣∣S0

g

∣∣ : g is a CvRDF on G}. By Lemma 2, W1 ⊆ S0
g . Let

p ∈ V (Km). Set V1 = (W1 × {p}) ∪
[
((W1 ∪W2) ∩ S0

g )× (V (Km) \ {p})
]
, V2 = W2 × {p},

and V0 = (W0 × V (Km)) ∪ ((W1 \ S0
g ) × V (Km)). Let f = (V0, V1, V2). Then V 0

G = W0,
V 1
G = W1, and V 2

G = W2. Hence, g = h is a CvRDF on G. Also, S1
G ∪ S2

G = W1 ∪W2 is
convex in G since h is a CvRDF on G. Clearly, (iii) and (iv) of Theorem 10 is satisfied.
Hence, f is a CvRDF on G[Km] and

γCvR(G[Km]) ≤ ωG[Km](f) = |V1|+ 2|V2|
= |W1|+ (m− 1)|(W1 ∪W2) ∩ S0

g |+ 2|W2|
≤ |W1|+ 2|W2|+ (m− 1)|S0

g |
= ωCvR

G (g) + (m− 1)|S0
g | = k.

This proves the desired equality.

For each x ∈ S1
G ∪ S2

G, we write

T 0
x = {p ∈ V (H) : (x, p) ∈ V0},

T 1
x = {p ∈ V (H) : (x, p) ∈ V1}, and

T 2
x = {p ∈ V (H) : (x, p) ∈ V2}.

Theorem 11. Let G and H be connected non-complete graphs with γcl(G) ≥ 2. Then
f = (V0, V1, V2) is CvRDF on G[H] if and only if each of the following conditions hold:

(i) S1
G ∪ S2

G is a clique dominating set in G.

(ii) T 1
x ∪ T 2

x is a clique in H for each x ∈ S1
G ∪ S2

G.



R. Fortosa, S. Canoy Jr. / Eur. J. Pure Appl. Math, 17 (2) (2024), 1335-1351 1347

(iii) T 2
x is a (clique) dominating set in H for each x ∈ S0

G \NG(S
2
G).

Proof. Let f = (V0, V1, V2) be a CvRDF on G[H] such that γcl(G) ≥ 2. Then (i) and (ii)
hold by Theorem 4. Now, let x ∈ S0

G \NG(S
2
G) and let p ∈ V (H) \ (T 1

x ∪ T 2
x ). Since f is a

CvRDF on G[H], there exists (x, q) ∈ V2 such that (x, p)(x, q) ∈ E(G[H]). Hence, x ∈ S2
G

and there exists q ∈ T 2
x such that pq ∈ E(H). It follows that T 2

x is a dominating set in H,
showing that (iii) holds.

For the converse, suppose that (i), (ii), and (iii) hold. Let (x, p) ∈ V0. Then
x ∈ S0

G. If x ∈ (NG(S
2
G)), then there exists y ∈ S2

G ∩ NG(x). Let r ∈ T 2
y . Then

(y, r) ∈ V2 ∩ NG[H]((x, p)). If x /∈ (NG(S
2
G)), then there exists q ∈ T 2

x ∩ NH(p) by (iii).
Hence, (x, q) ∈ V2 ∩NG[H]

(
(x, p)

)
, Therefore, f is an RDF on G[H].

Now, let V1 ∪V2 =
⋃

x∈S [{x} × Tx]. Then S = S1
G ∪S2

G and Tx = T 1
x ∪T 2

x . By (i), (ii)
and Theorem 3, V1 ∪ V2 is convex in G[H]. Therefore, f is a CvRDF on G[H].

Corollary 5. Let G and H be connected non-complete graphs with γcl(G) ≥ 2. Then

γCvR(G[H]) = 2γcl(G).

Proof. Let D be a γcl-set in G and let p ∈ V (H). Let V1 = ∅, V2 = D × {p}, and
V0 = [(V (G) \ D) × V (H)] ∪ [D × (V (H) \ {p})]. Then S0

G = V (G) \ D, S1
G = ∅, and

S2
G = D. By assumption, S1

G ∪ S2
G = D is a clique dominating set in G. Also, T 2

x = {p} is
a clique set in H for each x ∈ S2

G. Moreover, S0
G \NG(S

2
G) = ∅. Hence, (i), (ii), and (iii)

of Theorem 11 hold. Therefore, f = (V0, V1, V2) is a CvRDF on G[H] and

γCvR(G[H]) ≤ ωCvR
G[H](f)

= 2|V2|
= 2γcl(G).

Now, let f = (V0, V1, V2) be a γCvR-function on G[H]. By Theorem 11, S1
G ∪ S2

G

is a clique dominating set in G. Since G is non-complete and γcl(G) ≥ 2, |S2
G| ≥ 2.

Furthermore, S2
G is a clique dominating set in G. Therefore,

γCvR(G[H]) = ωCvR
G[H](f) = |V1|+ 2|V2|

=
∑
x∈S1

G

|T 1
x |+ 2

∑
x∈S2

G

|T 2
x |

≥ |S1
G|+ 2|S2

G|
≥ 2γcl(G).

This proves the desired equality.

Theorem 12. Let G and H be non-complete connected graphs with γ(G) = 1. Then

γCvR(G[H]) =

{
2, if γ(H) = 1

4, if γ(H) ̸= 1



R. Fortosa, S. Canoy Jr. / Eur. J. Pure Appl. Math, 17 (2) (2024), 1335-1351 1348

Proof. If γ(H) = 1, then γ(G[H]) = 1. By Corollary 1, γCvR(G[H]) = 2. Next, let γ(H) ̸=
2. Let v be a dominating vertex ofG. Pick any w ∈ NG(v) and p ∈ V (H). Let V0 = [V (G)\
{v, w} × V (H)] ∪ [{v, w} × V (H) \ {p}], V1 = ∅, and
V2 = {v, w} × {p}. Let (x, q) ∈ V0. If x ∈ V (G) \ {v, w}, then xv ∈ E(G). Hence,
(v, p) ∈ V2 and (x, q)(v, p) ∈ E(G[H]). If x = v, then (w, p) ∈ V2 ∩ NG[H]((x, q)) and if
x = w, then (v, p) ∈ V2 ∩ NG[H]((x, q)). Therefore, g = (V0, V1, V2) is an RDF on G[H].
Now, V1 ∪ V2 = V2 and ⟨V2⟩ ∼= K2. Hence, V1 ∪ V2 is convex in G[H]. This shows that g
is a CvRDF on G[H]. Since ωCvR

G[H](g) = 2|V2| = 4, γCvR(G[H]) = 4 by Proposition 3.

The Cartesian product G × H of two graphs G and H is the graph with
V (G×H) = V (G)× V (H) and (u, u′)(v, v′) ∈ E(G×H) if and only if either uv ∈ E(G)
and u′ = v′ or u = v and u′v′ ∈ E(H).

Lemma 3. Let G and H be a connected graphs. If f = (V0, V1, V2) is a CvRDF on G□H
then V1 ∪ V2 = (S1

G ∪ S2
G)× (S1

H ∪ S2
H).

Proof. If (x, p) ∈ V1, then x ∈ S1
G and p ∈ S1

H . Thus (x, p) ∈ S1
G × S1

H . Also, if
(x, p) ∈ V2, x ∈ S2

G and p ∈ S2
H . Thus (x, p) ∈ S2

G × S2
H . Hence,

V1 ∪ V2 ⊆ (S1
G ∪ S2

G)× (S1
H ∪ S2

H).
Now, let (z, q) ∈ (S1

G∪S2
G)×(S1

H ∪S2
H). Suppose that (z, q) ∈ V0. Suppose z ∈ S1

G and
q ∈ S1

H . Since f is an RDF, there exists (w, t) ∈ V2 ∩NG[H]((z, q)). Suppose w = z. Then
tq ∈ E(H). Let y ∈ V (G) such that (y, q) ∈ V1. Let
P (y, z) = [y1, y2, . . . , yk] where y1 = y and yk = z be a y-z geodesic in G for some
k ≥ 1. Then, P ((y, q), (z, t)) = [(y1, q), (y2, q), . . . , (yk, q), (z, t)] is also (y, q)-(z, t) geodesic
in G□H, a contradiction to our assumption that V1 ∪ V2 is convex. Suppose w ̸= z. Then
wz ∈ E(G) and t = q. Since z ∈ S1

G, there exists r ∈ V (H) such that (z, r) ∈ V1. Let
P (q, r) = [q1, q2, . . . , qm, z] where q1 = q and qm = r be a q − r geodesic in H. Then
P ((w, q)(z, r)) = [(w, q), (z, q1), (z, q2), . . . , (z, qm)] is a (w, q)-(z, r) geodesic in G□H, a
contradiction to our assumption that V1 ∪V2 is convex. Similar arguments can be used to
show that a contradiction is obtained when z ∈ S1

G, q ∈ S2
H or z ∈ S2

G, q ∈ S1
H or z ∈ S1

G,
q ∈ S2

H .
Therefore (z, q) ∈ V1 ∪ V2 showing that (S1

G ∪ S2
G)× (S1

H ∪ S2
H) ⊆ V1 ∪ V2. This proves

the desired equality.

Theorem 13. Let G and H be a connected graphs. Then f = (V0, V1, V2) is a CvRDF on
G□H if and only if the following conditions hold:

(i) for each x ∈ S0
G and p ∈ T 0

x , there exists q ∈ T 2
x ∩ NH(p) or y ∈ S2

G ∩ NG(x) with
q = p ∈ T 2

y

(ii) V1 ∪ V2 = (S1
G ∪ S2

G)× (S1
H ∪ S2

H) and

(a) S1
G ∪ S2

G is a convex dominating set in G and S1
H ∪ S2

H = V (H) or

(b) S1
H ∪ S2

H is a convex dominating set in G and S1
G ∪ S2

G = V (G).



R. Fortosa, S. Canoy Jr. / Eur. J. Pure Appl. Math, 17 (2) (2024), 1335-1351 1349

Proof. Let f = (V0, V1, V2) be a CvRDF on G□H and let x ∈ S0
G and p ∈ T 0

x . Then
(x, p) ∈ V0. This shows that (i) holds. By Lemma 3, V1 ∪ V2 = (S1

G ∪ S2
G) × (S1

H ∪ S2
H).

Hence, by Theorem 6, (ii) holds.
Conversely, suppose that (i) and (ii) hold. By (i). Let (x, p) ∈ V0. Then x ∈ S0

G and
p ∈ T 0

x . By (i), there exists (y, q) ∈ NG□H

(
(x, p)

)
. This implies that f is an RDF on

G□H. By (a) and (b), S1
G ∪ S2

G and S1
H ∪ S2

H are convex sets in G and H, respectively.
Hence, by Theorem 5, V1 ∪ V2 is convex in G□H. Therefore, f is a CvRDF on G□H.

Corollary 6. Let G and H be connected graphs of orders m and n, respectively. Then

γCvR(G□H) ≤ min{n · γCvR(G),m · γCvR(H)}.

Proof. Let g = (W0,W1,W2) be a γCvR-function on G. Set V0 = W0 × V (H),
V1 = W1 × V (H), and V2 = W2 × V (H). Let f = (V0, V1, V2). Then S0

G = W0,
S1
G = W1, and S2

G = W2. Hence, S1
G ∪ S2

G = W1 ∪ W2 is a convex dominating set in
G and S1

H ∪ S2
H = V (H). Hence, by Theorem 13, f = (V0, V1, V2) is a CvRDF on G□H

and

γCvR(G□H) ≤ ωCvR
G□H(f)

= |V1|+ 2|V2|
= |W1 × V (H)|+ 2|W2 × V (H)|
= |V (H)| × (|W1|+ 2|W2|)
= n(|W1|+ 2|W2|)
= n · γCvR(G).

A similar argument is used to show that γCvR(G□H) ≤ m · γCvR(H). Hence,
γCvR(G□H) ≤ min{n · γCvR(G),m · γCvR(H)}.

Remark 2. The bound given in Corollary 6 is sharp. It can be verified that for any
connected graph H of order m, γCvR(Kn□H) = 2m = γCvR(Kn) ·m.

4. Conclusion

The concept of convex Roman domination in a graph has been investigated further
in this study. Specifically, convex Roman dominating functions on graphs resulting from
the corona, edge corona, complementary prism, lexicographic, and Cartesian product of
graphs have been characterized. These characterizations have been utilized to derive
bounds or exact values for the convex Roman domination number of each of these graphs.
Interested researchers may investigate this concept for other graphs not considered in
this paper. Moreover, it may be interesting to investigate the complexity of the convex
Roman domination problem and explore some relationships, if any, of this newly defined
parameter with other existing and related parameters to it.



REFERENCES 1350

Acknowledgements

The authors would like to thank the referees for the invaluable comments and sugges-
tions they gave us which led to the improvement of the paper. The authors are also grateful
to the Department of Science and Technology - Accelerated Science and Technology Hu-
man 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-
oritical 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] G. Chartrand, J. Fink, and P. Zhang. Convexity in Graphs. Discrete Applied Math-
ematics, (116):115–126, 2002.

[7] M. Chellali, T.W. Haynes, and S.T. Hedetnieme. Roman {2} domination. Discrete
Applied Math, 204:22–28, 2016.

[8] 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.

[9] E.L. Enriquez and S.R. Canoy Jr. On a variant of convex domination in a graph.
International Journal of Mathematical Analysis, 9(32):1585–1592, 2015.

[10] R.J. Fortosa and S.R. Canoy Jr. Convex Roman dominating function in graphs.
European Journal of Pure and Applied Mathematics, 16(3):1705–1716, 2023.

[11] F. Harary and J. Nieminen. Convexity in graphs. Journal of Differential Geometry,
16(2):185–190, 1981.

[12] T.W. Haynes, S.T. Hedetneme, and P.J. Slater. Distance in Graphs. Marcel Dekker,
New York, 1980.



REFERENCES 1351

[13] M.A. Henning, W.F. Klostermeyer, and G. MacGillivray. Perfect Roman domination
in trees. Discrete Applied Mathematics, 236:235–245, 2018.

[14] S.R. Canoy Jr. A short note on convexity and convex domination in G[Km]. Applied
Mathematical Sciences, 8(115):5737–5741, 2014.

[15] S.R. Canoy Jr and I.J.L. Garces. Convex sets under some graph operations. Graphs
and Combinatorics, 18(4):787–793, 2002.

[16] K. Kammerling and L. Volkman. Roman k-domination in graphs. Journal of the
Korean Mathematical Society, 46(6):1309–1318, 2009.

[17] M.A. Labendia and S.R. Canoy Jr. Convex Dominatioin in the composition and
Cartesian product of graphs. Czechoslovak Mathematical Journal, 62:1003–1009, 2012.

[18] M. Lemanska. Weakly convex and convex domination numbers. Opuscula Mathemat-
ica, 24(2):181–188, 2004.

[19] M.H. Muddebiha and Sumangaladevi. Connected Roman domination in graphs. In-
ternational Journal of Research and Engineering Technology, 2(10):333–340, 2013.

[20] L.M. Paleta and F.P. Jamil. On perfect Italian domination in graphs. Discrete
Mathematics, Algorithms and Applications, page 2350085, 2023.

[21] I.M. Pelayo. On convexity in graphs. Technical report, Online: http://www. ma3.
upc. es/users/pelayo/research/Definitions. pdf., pages 1–21, 2004.

[22] 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.

[23] C.S. ReVelle and K.E. Rosing. Defendens imperium romanum: a classical problem
in military strategy. Amerrican Mathematical Monthly, 107(7):585–594, 2000.

[24] I. Stewart. Defend the Roman Empire! Scientific American, 281(6):136–138, 1999.