EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS
2025, Vol. 18, Issue 2, Article Number 5973
ISSN 1307-5543 – ejpam.com
Published by New York Business Global

Hop k-Rainbow Domination in Graphs

Jamil J. Hamja1,2, Seyed Mahmoud Sheikholeslami3,∗, Imelda S. Aniversario2,4,
Lyster Rey B. Cabardo2,4
1 Mathematics and Sciences Department, College of Arts and Sciences, MSU-Tawi-Tawi
College of Technology and Oceanography, 7500 Tawi-Tawi, Philippines
2 Department of Mathematics and Statistics, College of Science and Mathematics,
Mindanao State University-Iligan Institute of Technology, 9200 Iligan City, Philippines
3 Department of Mathematics, Azarbaijan Shahid Madani University, Tabriz, Iran
4 Center for Mathematical and Theoretical Physical Sciences, Premier Research Institute of
Science and Mathematics (PRISM), Mindanao State University-Iligan Institute of
Technology, 9200 Iligan City, Philippines

Abstract. Let G = (V (G), E(G)) be a graph. A function f that assigns to each vertex
of G a subset of colors from the set {1, 2, . . . , k}, i.e., f : V (G) → P ({1, 2, 3, . . . , k}), is called
a hop k-rainbow dominating function (HkRDF) of G if for every vertex v ∈ V (G) with f(v) = ∅,
we have

⋃
u∈N2

G(v) f(u) = {1, 2, . . . , k} where N2
G(v) is the set of vertices of G at distance two

from v. The weight of f , denoted ω(f), is defined as ω(f) =
∑

x∈V (G) |f(x)|. The hop k-rainbow
domination number of G, denoted γhrk(G), is the minimum weight of a hop k-rainbow dominating
function of G. A hop k-rainbow dominating function of G with weight γhrk(G) is a γhrk-function
of G. In this paper, we initiate the study of hop k-rainbow domination in graphs. We begin by
exploring fundamental properties of this parameter and then establish various bounds on γhrk(G).
Furthermore, we identify the graphs for which γhrk(G) = n and determine exact values for certain
graph classes, including complete graphs, complete bipartite graphs, paths, and cycles. Addition-
ally, for any positive integer a, we construct connected graphs satisfying γhr2(G) = γr2(G) = a.
Finally, we provide a characterization of all graphs where γhr2(G) = n.

2020 Mathematics Subject Classifications: 05C69

Key Words and Phrases: Hop domination number, k-rainbow domination number, hop k-
rainbow domination number

∗Corresponding author.
DOI: https://doi.org/10.29020/nybg.ejpam.v18i2.5973

Email addresses: jamilhamja@msutawi-tawi.edu.ph (J. J. Hamja),
s.m.sheikholeslami@azaruniv.ac.ir (S. M. Sheikholeslami),
imelda.aniversario@g.msuiit.edu.ph (I. S. Aniversario),
lysterrey.cabardo@g.msuiit.edu.ph (L. B. Cabardo)

https://www.ejpam.com 1 Copyright: © 2025 The Author(s). (CC BY-NC 4.0)



J. J. Hamja et al. / Eur. J. Pure Appl. Math, 18 (2) (2025), 5973 2 of 17

1. Introduction

Domination in graphs is frequently used as a model for real-world applications, where
the vertices in a dominating set provide a service or product that must be accessible to
every vertex in the network. In 2020, Haynes et al. ([1]) published a comprehensive survey
on domination in graphs. Rainbow domination extends this concept by introducing mul-
tiple service types, represented by different colors, and ensuring that every vertex without
direct service has access to all service types in its neighborhood. Rainbow domination is
being studied because it has a lot to do with domination in Cartesian products of graphs
and what that means for Vizing’s conjecture, even though its practical uses are still un-
known. The rainbow domination number was first proposed by Brešar et al. in 2008 [2].
They showed how it works in paired-domination within Cartesian products of graphs and
explained how it is related to standard domination. Later, in 2014, Z. Shao determined
bounds for the k-rainbow domination number of any arbitrary graph for any positive inte-
ger k [3]. Since then, this concept has been widely explored (see, for example, [4–9]).

In this paper, we introduce the study of hop k-rainbow domination in graphs, integrat-
ing the ideas of hop domination and k-rainbow domination parameters. The incorporation
of hop distance constraints influences the behavior of minimum rainbow dominating func-
tions, leading to new theoretical bounds and extremal results. The concept of a hop
dominating set was first proposed by Natarajan et al. in 2015 [10], and it has since been
expanded by many researchers who have applied it to various domination variants. For
more details on hop domination, see for instance, [11–14].

2. Terminology and Notation

Let G be a graph with the vertex set V (G) and the edge set E(G), and of order
n = |V (G)| and size m = |E(G)|. The set of neighbors of a vertex u in G is called the open
neighborhood of u in G, denoted by NG(u) = {v ∈ V (G) : uv ∈ E(G)}. The closed neigh-
borhood of u in G is the set NG[u] = NG(u)∪ {u} and the closed neighborhood of a subset
S of V (G) is the set NG[S] = NG(S) ∪ S. The degree of a vertex u in G is the number of
neighbors u in G, denoted by deg(u). The maximum (minimum) degree among the vertices
of G is denoted by ∆(G) (δ(G), respectively). The distance dG(u, v) between two vertices
u and v in a connected graph G is the length of a shortest u-v path in G while the diameter
of G, denoted by diam(G), is the maximum distance among all pairs of vertices in G. A
complete graph on n vertices is denoted by Kn, while a complete bipartite graph with partite
sets of size p and q is denoted by Kp,q. We write Pn for the path of order n, Cn for the cycle
of length n and Kn for the graph with n vertices and no edges, as defined by Harary in [15].

A vertex v in G is called an ℓ-neighbor of a vertex u in G if dG(u, v) = ℓ. The set
N ℓ

G(u) = {v ∈ V (G) : dG(v, u) = ℓ} is called the open ℓ-neighborhood of u. The closed
ℓ-neighborhood of u in G is given by N ℓ

G[u] = N ℓ
G(u) ∪ {u}. The open ℓ-neighborhood of

X ⊆ V (G) is the set N ℓ
G(X) =

⋃
u∈X N ℓ

G(u). The closed ℓ-neighborhood of X in G is the



J. J. Hamja et al. / Eur. J. Pure Appl. Math, 18 (2) (2025), 5973 3 of 17

set N ℓ
G[X] = N ℓ

G(X) ∪X.

A set S ⊆ V (G) is said to be a dominating set if NG[S] = V (G). A dominating set S
is a minimal dominating set if no proper subset of S is a dominating set. The domination
number of a graph G, denoted by γ(G), is the minimum cardinality of a dominating set
of G. A dominating set S with the cardinality equal to γ(G) is said to be a γ-set of G or
γ(G)-set.

A set S ⊆ V (G) is a hop dominating set of G if N2
G[S] = V (G), that is, for every

v ∈ V (G) \ S, there exists u ∈ S such that dG(u, v) = 2. The hop domination number
of G, denoted by γh(G), is The minimum cardinality of a hop dominating set of G. A
hop dominating set with cardinality equal to γh(G) is called a γh-set of G, as defined by
Natarajan et al. in [10]. For a positive integer ℓ, the ℓ-degree of a vertex v in a graph
G, denoted by degℓ(v), is defined as the number of vertices at distance ℓ from v in G.
The maximum ℓ-degree among the vertices of G is denoted by ∆ℓ(G). In the special case
ℓ = 2, a 2-neighbor is called a hop-neighbor, denoted by N2

G(u). The 2-degree is called
the hop-degree, denoted by deg2(v). The maximum hop-degree among the vertices of G is
denoted by ∆h(G), as defined by Shabani et al. in [16].

A function f : V → {0, 1, 2} is a Roman dominating function (RD-function, for short)
on G if every vertex u ∈ V for which f(u) = 0 is adjacent to at least one vertex v for which
f(v) = 2, as defined by E. J. Cockayne in [17]. A hop Roman dominating function (HRD-
function) of G is a function g defined on V (G) into {0, 1, 2} having the property that for
every vertex u ∈ V with g(u) = 0 there is a vertex w with g(w) = 2 and d(u,w) = 2. The
hop Roman domination number γhR(G) is equal to the minimum weight of a HRD-function
in G. For more details on hop Roman domination see for example [16].

Let G be a graph and let f be a function that assigns to each vertex a set of colors
chosen from the set {1, 2, 3, . . . , k}, that is, f : V (G) → P ({1, 2, 3, . . . , k}). If for each
vertex v ∈ V (G) with f(v) = ∅, we have

⋃
u∈NG(v) f(u) = {1, 2, 3, . . . , k}, then f is called

the k-rainbow dominating function (kRDF) of G. The weight ω(f) of f is defined as
ω(f) =

∑
v∈V (G)|f(v)|. The k-rainbow domination number of G, denoted by γrk(G), is the

minimum weight of a kRDF. A k-rainbow dominating function of G with weight γrk(G) is
a γrk-function of G, as defined by B. Brešar in [2].

A function f : V (G) → P ({1, 2, . . . , k}) is a hop k-rainbow dominating function
(HkRD-function) if for every vertex v ∈ V (G) with f(v) = ∅, we have

⋃
u∈N2

G(v) f(u) =

{1, 2, . . . , k}. The weight of a hop k-rainbow dominating function is ω(f) =
∑

v∈V (G) |f(v)|.
The hop k-rainbow domination number of G, denoted γhrk(G), is the minimum weight of
a hop k-rainbow dominating function of G. A hop k-rainbow dominating function of
G with weight γhrk(G) is a γhrk-function of G. For the sake of simplicity, we will write
HkRD-number instead of hop k-rainbow domination number. Clearly, when k = 1, γh1r(G)
matches with the usual hop domination number γh(G).



J. J. Hamja et al. / Eur. J. Pure Appl. Math, 18 (2) (2025), 5973 4 of 17

Example 1. Consider the graph G in Figure 1. Let S = {v1, v2, v5, v6, v7, v8} and let
f : V (G) → P ({1, 2}) be a function defined by f(v1) = f(v5) = f(v7) = f(v8) = {2},
f(v2) = f(v6) = {1}, and f(v3) = f(v4) = ∅. Observe that dG(v3, v1) = 2, and
dG(v4, v2) = 2. Thus, S is a hop dominating set of G. Further, notice that

⋃
u1∈N2

G(v3)
f(u1) =

{1, 2} and
⋃

u2∈N2
G(v4)

f(u2) = {1, 2}. Then f is a hop 2-rainbow dominating function of
G. The weight of f is given

ω(f) = |f(v1)|+ |f(v2)|+ |f(v3)|+ |f(v4)|+ |f(v5)|+ |f(v6)|+ |f(v7)|+ |f(v8)|
= 1 + 1 + 0 + 0 + 1 + 1 + 1 + 1

= 6.

v1 v2

v3

v4

v5

v6

v7 v8
G :

Figure 1: A graph G of order 8 with a hop 2-rainbow dominating function of weight 6.

3. Preliminary Results

In this section, we study the basic properties of HkRD-function and we establish various
bounds for HkRD-number of a graph G.

Theorem 1. Let k be a positive integer, and let G be a graph of order n = n1+n2+· · ·+np

with p disjoint components G1, G2, . . . , Gp with n1, n2, . . . , np vertices, respectively. Then

γhrk(G) =

p∑
i=1

γhrk(Gi).

Proof. Let G be a graph of order n = n1 + n2 + · · · + np consisting of p disjoint
components G1, G2, . . . , Gp, where each Gi has ni vertices.

First, for each i ∈ {1, 2, . . . , p}, let fi be a γhrk-function of Gi, meaning that fi is a
hop k-rainbow dominating function of Gi of weight ω(fi) = γhrk(Gi). Define a function
f : V (G) → P({1, 2, . . . , k}) by f(v) = fi(v) if v ∈ V (Gi), for each i ∈ {1, 2, . . . , p}.
Since G1, G2, . . . , Gp are disjoint, it follows that f is a hop k-rainbow dominating function
of G of weight ω(f) =

∑p
i=1 ω(fi). By the minimality of γhrk(G), we obtain

γhrk(G) ≤ ω(f) =

p∑
i=1

γhrk(Gi).



J. J. Hamja et al. / Eur. J. Pure Appl. Math, 18 (2) (2025), 5973 5 of 17

Conversely, suppose f ′ is a γhrk-function of G. Since the components of G are disjoint,
we can define f ′

i as the restriction of f ′ to Gi, i.e., f ′
i = f ′|V (Gi). Since each f ′

i is a hop k-
rainbow dominating function of Gi, we have ω(f ′

i) ≥ γhrk(Gi). Thus, ω(f ′) =
∑p

i=1 ω(f
′
i) ≥∑p

i=1 γhrk(Gi). Since f ′ is an optimal function for G, it follows that

γhrk(G) = ω(f ′) ≥
p∑

i=1

γhrk(Gi).

From the two inequalities, we conclude that

γhrk(G) =

p∑
i=1

γhrk(Gi).

This completes the proof.

Thus, in the following discussion, we consider only connected graphs.
For any graph G and a γhrk-function f of G, define the set

V f
i = {x ∈ V (G) | |f(x)| = i}, for i ∈ {0, 1, . . . , k}.

Example 2. Consider the graph G in Figure 1 and let f : V (G) → P({1, 2}) be the
hop 2-rainbow dominating function of G defined in Example 1. Then, the sets of vertices
corresponding to each function value are as follows:

V f
0 = {v3, v4}, V f

1 = {v1, v2, v5, v6, v7, v8}, V f
2 = ∅.

Let G be a connected graph and consider the graph G2 whose vertex set is V (G), where
two vertices u and v are adjacent in G2 if dG(u, v) = 2. Clearly, any kRD-function of G2

is an HkRD-function of G and vice versa. Thus, we have the following.

Remark 1. For any graph G, γhrk(G) = γrk(G
2).

Remark 2. If G is a graph of order n ≥ 1 with δ(G) ≥ 1. Let f be a γhrk-function of G,
then

(i) n =
∑k

j=0|V
f
j |,

(ii) γhrk(G) =
∑k

j=1 j|V
f
j |, and

(iii) |V f
0 | ≥

∑k
j=2(j − 1)|V f

j |.

Proof. Suppose G is a graph of order n ≥ 1 with δ(G) ≥ 1, and let f be a γhrk-function
of G. By definition, V f

i = {v ∈ V (G) : |f(v)| = i} for each i ∈ {0, 1, . . . , k}. Since every
vertex belongs to exactly one of these sets, we have n =

∑k
j=0|V

f
j |. Hence, (i) holds. Since

ω(f) =
∑

v∈V (G) |f(v)|, we can rewrite this sum in terms of V f
j by γhrk(G) =

∑k
j=1 j|V

f
j |.

Therefore, (ii) holds. Let v be any vertex in G with f(v) = ∅. Then
⋃

u∈N2
G(v) f(u) =



J. J. Hamja et al. / Eur. J. Pure Appl. Math, 18 (2) (2025), 5973 6 of 17

{1, 2, . . . , k}. This implies that vertices in V f
0 rely on vertices in V f

j for j ≥ 2 to contribute
enough colors. Since each vertex in V f

j contributes j colors, but at least one color is
required per vertex in V f

0 , it follows that |V f
0 | ≥

∑k
j=2(j − 1)|V f

j |. This proves (iii). The
proof is complete.

Theorem 2. Let k be a positive integer and G be a graph of order n = n1 +n2 + · · ·+np.
If G is a disjoint union of cliques and isolates, then γhrk(G) = n.

Proof. Assume that G is a disjoint union of cliques and isolates. Let
G =

⋃p
i=1Gi, where Gi = Kr for some r ≥ 1. By Theorem 1, γhrk(G) =

∑p
i=1 γhrk(Gi).

Therefore, we have

γhrk(G) =

p∑
i=1

γhrk(Gi) =

p∑
i=1

|V (Gi)| = n1 + n2 + · · ·+ np = n.

The next result is a direct consequence of Theorem 2.

Corollary 1. Let k and n be positive integers. Then

γhrk(Kn) = γhrk(Kn) = n.

Theorem 3. Let k ≥ 2 be an integer and let G be a connected graph of order n ≥ k + 1.
Then

γhrk(G) ≥ k + 1.

Moreover, the bound is sharp for stars K1,m (m ≥ k).

Proof. Since G is a connected graph of order n ≥ k + 1, we assume γhrk(G) = k. Let
S = V (G) \ V g

0 , that is the set of vertices assigned at least one color. Given n ≥ k + 1, it
follows that V g

0 ̸= ∅. Now, consider any x ∈ V g
0 and any y ∈ S. Since x is not assigned a

color, there exist a vertex z such that z ∈ NG(x)∩NG(y), ensuring x is at distance 2 from
y. However, since x is at distance 2 from every vertex in S, it follows that z /∈ S, meaning
z ∈ V g

0 . But then, z would also need to be assigned the set of colors from some vertex in
S, contradicting the assumption that γhrk(G) = k. Therefore, γhrk(G) ≥ k + 1.

Theorem 4. Let k ≥ 1 be an integer and G be a graph of order n ≥ 1. Then

min{n, k + 1} ≤ γhrk(G) ≤ n.

In particular, if 1 ≤ n ≤ k + 1, then γhrk(G) = n.

Proof. If n ≥ k + 1, then it follows from Theorem 3 that γhrk(G) ≥ k + 1. Let
n ≤ k and let g be γhrk-function of G. If V g

0 ̸= ∅ and v ∈ V g
0 , then by the definition we

have
⋃

u∈N2
G(v) g(u) = {1, 2, . . . , k}, and so γhrk(G) ≥

∑
u∈N2

G(v) |g(u)| ≥ k ≥ n. Assume



J. J. Hamja et al. / Eur. J. Pure Appl. Math, 18 (2) (2025), 5973 7 of 17

that V g
0 = ∅. Then by Remark 2, we have γhrk(G) =

∑k
j=1 j|V

f
j | ≥

∑k
j=1 |V

f
j | = n.

Consequently, we have γhrk(G) ≥ min{n, k + 1}.
For the upper bound, consider the function h : V (G) → P({1, 2, . . . , k}) defined by

h(v) = {1} for all v ∈ V (G). Clearly, h is an HkRD-function of G of weight n leading to
γhrk(G) ≤ n.

Therefore, we have established that min{n, k + 1} ≤ γhrk(G) ≤ n. In particular, if
n ≤ k+1, then the lower bound is the min{n, k+1} = n, implying that γhrk(G) = n.

Proposition 1. Let k ≥ 2 be an integer and G be a graph of order n ≥ k with δ(G) ≥ n−2.
Then γhrk(G) = n.

Proof. Let f be a γhrk-function of G such that |V f
0 | is minimized. If V f

0 = ∅, then we
are done. Assume, for contradiction, that V f

0 ̸= ∅ and let x ∈ V f
0 . Hence, we must have⋃

u∈N2
G(x) f(u) = {1, 2, . . . , k}. It follows from δ(G) ≥ n − 2 that |N2

G(x)| = 1. Assume
that y ∈ N2

G(x). Then f(y) = {1, 2, . . . , k}. Since y is adjacent to all vertices other than
x, the function g defined on g(x) = g(y) = {1} and g(z) = f(z) for other vertices is an
HkRD-function of G of weight at most ω(f) with |V g

0 | < |V f
0 |, contradicting the choice of

f . Therefore, V f
0 = ∅, and it follows that γhrk(G) = ω(f) = n.

In the next theorem we provide a sufficient condition for a graph G to have γhrk(G) = n.

Theorem 5. For positive integers n and k ≥ 2, let G be a graph of order n ≥ k with
k > ∆h(G

2). Then γhrk(G) = n.

Proof. Suppose, for the sake of contradiction, that γhrk(G) < n. Let f be a γhrk-
function of G such that |V f

0 | is as large as possible, where V f
0 = {v ∈ V (G) : f(v) = ∅}.

Since γhrk(G) < n, there is a vertex v ∈ V f
0 and by the definition we have

⋃
x∈N2

G(v) f(x) =

{1, 2, . . . , k}. Since k > ∆h(G
2), there exists a vertex x ∈ N2

G(v) such that |f(x)| ≥
∆h(G) + 1. Assume, without loss of generality, that {1, 2, . . . ,∆h(G) + 1} ⊆ f(x). Let
x1, x2, . . . , xdeg2(x) be the vertices of G at distance 2 from x and define the function
g : V (G) → P({1, 2, . . . , k}) by g(xi) = f(xi) ∪ {i} for each i ∈ {1, 2, . . . ,deg2(x)},
g(x) = f(x) − {1, . . . ,deg2(x)} and g(y) = f(y) for other vertices. Then g is an HkRD-
function of G of weight ω(f) such that |V g

0 | < |V f
0 | a contradiction with the choice of f .

Consequently, γhrk(G) = n.

The next result is immediate from Theorem 5.

Corollary 2. For positive integers n and k with n ≥ k ≥ 5,

γhrk(Pn) = γhrk(Cn) = n.

Theorem 6. Let k ≥ 1 be an integer and G be a connected graph of order n ≥ k with hop
maximum degree ∆h. Then γhrk(G) ≥ nk/(∆h + k).



J. J. Hamja et al. / Eur. J. Pure Appl. Math, 18 (2) (2025), 5973 8 of 17

Proof. Let g be a γhrk-function of G, i.e ω(g) = γhrk(G), and let V g
0 be the set

of vertices assigned ∅ under g. Clearly, γhrk(G) ≥ n − |V g
0 |. On the other hand, sine

each vertex x in V g
0 must have each of k colors in N2

G(x), we have ∆hγhrk(G) ≥ k|V g
0 |.

Since γhrk(G) ≥ n − |V g
0 |, it would imply that kγhrk(G) ≥ kn − k|V g

0 |. Moreover, since
k|V g

0 | ≤ ∆hγhrk(G), it follows that kγhrk(G)+∆hγhrk(G) ≥ kn. Hence, (k+∆h)γhrk(G) ≥
kn. Therefore, γhrk(G) ≥ nk/(∆h + k) as desired.

The next result will be used in the subsequent discussion.

Proposition 2. [18] For any positive integer n, we have:

γrk(Kn) =

{
k, if n ≥ k,

n, if n < k.

Proposition 3. Let m, n, and k be positive integers with k ≥ 1 and m ≤ n. Then

γhrk(Km,n) =


2k if m ≥ k,

k +m if m < k and n ≥ k,

m+ n if n < k.

Proof. It is easy to see that K2
m,n = Km ∪ Kn. By Proposition 2, for any positive

integer s, we have γrk(Ks) = min{k, s}. So, applying Remark 1 yields

γhrk(Km,n) = γrk(K
2
m,n) = γrk(Km) + γrk(Kn) = min{k,m}+min{k, n},

as desired.

In the next theorem we provide an upper and a lower bound on the hop k-rainbow
domination number in terms of hop domination number. We recall that γh(Kn) = n and
γh(Km,n) = 2 (see [10]).

Theorem 7. Let k ≥ 2 be an integer and let G be a graph of order n ≥ k. Then

γh(G) ≤ γhrk(G) ≤ kγh(G).

Moreover, these bounds are sharp.

Proof. We first show that the left inequality holds. Let f be a γhrk-function of G.
Then clearly the set S = {v ∈ V (G) : f(v) ̸= ∅} is a hop dominating set of G. Therefore,
|S| ≥ γh(G). Since the weight ω(f) =

∑
v∈V (G) |f(v)| and |f(v)| ≥ 1 for each v ∈ S, it

follows that ω(f) ≥ |S| ≥ γh(G). This implies that γh(G) ≤ γhrk(G).
Next, we will show that γhrk(G) ≤ kγh(G). Consider a minimum hop dominating

set S of G with |S| = γh(G). Define a function f : V (G) → P({1, 2, . . . , k}) by f(v) =
{1, 2, . . . , k} for each vertex v ∈ S and f(v) = ∅ for every v ∈ V (G) \ S. For each
v ∈ V (G)\S, there exists a vertex u ∈ S such that d(u, v) = 2 since S is a hop dominating
set. Since f(u) = {1, 2, . . . , k} for each u ∈ S, it follows that

⋃
u∈N2

G(v) f(u) = {1, 2, . . . , k}



J. J. Hamja et al. / Eur. J. Pure Appl. Math, 18 (2) (2025), 5973 9 of 17

for each v ∈ V (G) \ S. Thus, f is a hop k-rainbow dominating function of G of weight
ω(f) = kγh(G). Hence, we have γhrk(G) ≤ kγh(G).

For the sharpness of the lower bound, let G = Kn. Then by Corollary 1, we have
γh(G) = γhrk(G). For the upper bound, let G = Km,n, where n ≥ m ≥ k. Then by
Proposition 3, we have γhrk(Km,n) = 2k = kγh(Km,n).

4. Exact values

The exact values of the k-rainbow domination number for k ∈ {2, 3} of paths and cycles
are determined as follows.

Theorem 8. [3, 6] Let n be a positive integer. Then
(i) γr2(Pn) =

⌊
n
2

⌋
+ 1.

(ii) For n ≥ 3, γr2(Cn) =
⌊
n
2

⌋
+
⌈
n
4

⌉
−

⌊
n
4

⌋
.

(iii) For n ≥ 5, γr3(Pn) =


⌈
3n
4

⌉
+ 1 if n ≡ 0 (mod 4),⌈

3n
4

⌉
if n ≡ 1, 2, 3 (mod 4).

(iv) For n ≥ 5, γr3(Cn) =
⌈
3n
4

⌉
.

Using Theorem 8 and Proposition 1, we determine the exact value of hop k-rainbow
domination number for k ∈ {2, 3} of paths and cycles in the next Theorem.

Theorem 9. Let n be a positive integer. Then

(i) γhr2(Pn) =


⌊
n+1
4

⌋
+
⌊
n−1
4

⌋
+ 2 if n ≡ 1, 3 (mod 4),

2
⌊
n
4

⌋
+ 2 if n ≡ 0, 2 (mod 4).

(ii) For n ≥ 2, γhr3(Pn) =



2
⌈
3n
8

⌉
+ 2 if n ≡ 0 (mod 8),⌈

3(n+1)
8

⌉
+
⌈
3(n−1)

8

⌉
+ 1 if n ≡ 1, 7 (mod 8),

2
⌈
3n
8

⌉
if n ≡ 2, 4, 6 (mod 8),⌈

3(n+1)
8

⌉
+
⌈
3(n−1)

8

⌉
if n ≡ 3, 5 (mod 8).

(iii) For n ≥ 4, γhr2(Cn) =


⌊
n
2

⌋
+
⌈
n
4

⌉
−
⌊
n
4

⌋
if n ≡ 1 (mod 2),

2
(⌊

n
4

⌋
+

⌈
n
8

⌉
−
⌊
n
8

⌋)
otherwise.

(iv) For n ≥ 5, γhr3(Cn) =


⌈
3n
4

⌉
if n ≡ 1 (mod 2),

2
⌈
3n
8

⌉
otherwise.



J. J. Hamja et al. / Eur. J. Pure Appl. Math, 18 (2) (2025), 5973 10 of 17

Proof. Let Pn = [v1, v2, . . . vn] be a path on n vertices. By Theorem 4 and Proposition
1, we have γhr2(Pn) = γhr3(Pn) = n for n ∈ {1, 2, 3, 4}. Assume that n ≥ 5. If n is even,
then P 2

n is the union of two paths:

P = [v1, v3, . . . , vn−1] and Q = [v2, v4, . . . , vn].

If n is odd, then P 2
n is the union of two paths:

P ′ = [v1, v3, . . . , vn] and Q′ = [v2, v4, . . . , vn−1].

(i) Since both P and Q have n/2 vertices, we can use Theorem 8-(i) to find that
γr2(P ) =

⌊
n/2
2

⌋
+ 1 = ⌊n/4⌋+ 1, and similarly, γr2(Q) = ⌊n/4⌋+ 1. If n is even, then by

Remark 1, we obtain

γhr2(Pn) = γr2(P
2
n) = γr2(P ) + γr2(Q) = 2

(⌊n
4

⌋
+ 1

)
= 2

⌊n
4

⌋
+ 2,

as desired. Assume that n is odd. Then P and Q have lengths n+1
2 and n−1

2 , respec-

tively. Applying Theorem 8-(i) again, we obtain γr2(P ) =
⌊
(n+1)/2

2

⌋
+ 1 =

⌊
n+1
4

⌋
+ 1 and

γr2(Q) =
⌊
(n−1)/2

2

⌋
+ 1 =

⌊
n−1
4

⌋
+ 1. Therefore, by Remark 1, we have

γhr2(Pn) = γr2(P ) + γr2(Q) =

(⌊
n+ 1

4

⌋
+ 1

)
+

(⌊
n− 1

4

⌋
+ 1

)
.

Simplifying, we get

γhr2(Pn) =

⌊
n+ 1

4

⌋
+

⌊
n− 1

4

⌋
+ 2 =

⌊n
4

⌋
+
⌈n
4

⌉
+ 2,

as desired.

(ii) If n ≡ 0 (mod 8), then |V (P )| = n
2 ≡ 0 (mod 4), |V (Q)| = n

2 ≡ 0 (mod 4) and by
Remark 1 and Theorem 8-(iii), we have

γhr3(Pn) = γr3(P
2
n) = γr3(P ) + γr3(Q) = 2

(⌈
3n
2

4

⌉
+ 1

)
= 2

(⌈
3n

8

⌉
+ 1

)
,

as desired. If n ≡ 1 (mod 8) (the case n ≡ 7 (mod 8) is similar), then |V (P )| = n+1
2 ≡ 1

(mod 4) and |V (Q)| = n−1
2 ≡ 0 (mod 4). Applying Remark 1 and Theorem 8-(iii), it

follows that

γhr3(Pn) = γr3(P ) + γr3(Q)

=

⌈
3n+1

2

4

⌉
+

⌈
3n−1

2

4

⌉
+ 1



J. J. Hamja et al. / Eur. J. Pure Appl. Math, 18 (2) (2025), 5973 11 of 17

=

⌈
3(n+ 1)

8

⌉
+

⌈
3(n− 1)

8

⌉
+ 1.

If n ≡ 3 (mod 8) (the case n ≡ 5 (mod 8) is similar), then |V (P )| = n+1
2 ≡ 2 (mod 4)

and |V (Q)| = n−1
2 ≡ 1 (mod 4). Applying Remark 1 and Theorem 8-(iii), it follows that

γhr3(Pn) = γr3(P ) + γr3(Q)

=

⌈
3n+1

2

4

⌉
+

⌈
3n−1

2

4

⌉

=

⌈
3(n+ 1)

8

⌉
+

⌈
3(n− 1)

8

⌉
.

If n ≡ 2, 4, 6 (mod 8), then |V (P )| = |V (Q)| = n
2 ̸≡ 0 (mod 4). Applying Theorem

8-(iii), it follows that

γhr3(Pn) = γr3(P
2
n) = γr3(P ) + γr3(Q) = 2

⌈
3n
2

4

⌉
= 2

⌈
3n

8

⌉
.

(iii) Let Cn = [v1, v2, . . . , vn, v1] be a cycle on n vertices. By Theorem 4 and Remark
1, we have γhr2(C3) = 3 and γhr2(C4) = 4. Assume that n ≥ 5. If n is even, then C2

n is
the union of two cycles:

C = [v1, v3, . . . , vn−1, v1] and C ′ = [v2, v4, . . . , vn, v2],

of order n
2 . By Remark 1 and Theorem 8-(ii), we get

γhr2(Cn) = γr2(C
2
n)

= γr2(C) + γr2(C
′)

= 2

(⌊ n
2

2

⌋
+

⌈ n
2

4

⌉
−
⌊ n

2

4

⌋)
= 2

(⌊n
4

⌋
+
⌈n
8

⌉
−
⌊n
8

⌋)
,

as desired. Assume that n is odd. Then, clearly, C2
n = Cn, and by Theorem 8-(ii), we have

γhr2(Cn) = γr2(C
2
n) = γr2(Cn) =

⌊n
2

⌋
+
⌈n
4

⌉
−
⌊n
4

⌋
.

(iv) The proof is similar to that of item (iii). Let Cn = [v1, v2, . . . , vn, v1] be a cycle
of order n. We know from Theorem 4 and Remark 1 that γhr3(Cn) = γr3(C

2
n). Assume

that n ≥ 5. If n is odd. Then clearly C2
n = Cn. Hence, γhr3(Cn) = γr3(C

2
n) = γr3(Cn).

Applying Theorem 8(iv), we get

γhr3(Cn) =

⌈
3n

4

⌉
,



J. J. Hamja et al. / Eur. J. Pure Appl. Math, 18 (2) (2025), 5973 12 of 17

as desired. If n is even. Then C2
n is the union of two cycles, each of length n

2 :

C = [v1, v3, . . . , vn−1, v1] and C ′ = [v2, v4, . . . , vn, v2].

Thus,
γhr3(Cn) = γr3(C

2
n) = γr3(C) + γr3(C

′).

Since both C and C ′ are cycles of order n
2 , we can apply Theorem 8-(iv) again,

γr3(C) =
⌈
3n
2
4

⌉
=

⌈
3n
8

⌉
, and similarly, γr3(C ′) =

⌈
3n
8

⌉
. Hence,

γhr3(Cn) =

⌈
3n

8

⌉
+

⌈
3n

8

⌉
= 2

⌈
3n

8

⌉
,

This completes the proof.

Applying Theorem 9 and a similar method used in [3, 9], we obtain the following result.

Corollary 3. For any connected graph G of order n,

(i) γhr2(G) ≤


n+ 2− diam(G)

2 , if diam(G) ≡ 0 (mod 4),

n+ 1− diam(G)
2 , if diam(G) ≡ 2 (mod 4),

n+ 1− diam(G)+1
2 , if diam(G) ≡ 1 (mod 4),

n+ 1 + 1−diam(G)
2 , if diam(G) ≡ 3 (mod 4).

(ii) γhr3(G) ≤



n− diam(G) +
⌈
3diam(G)+6

8

⌉
+
⌈
3diam(G)

8

⌉
, if diam(G) ≡ 0, 6 (mod 8),

n− 1− diam(G) + 2
⌈
3diam(G)+3

8

⌉
, if diam(G) ≡ 1, 3, 5 (mod 8),

n− 1− diam(G) +
⌈
3diam(G)+6

8

⌉
+
⌈
3diam(G)

8

⌉
, if diam(G) ≡ 2, 4 (mod 8),

n+ 1 + 3−diam(G)
4 , if diam(G) ≡ 7 (mod 8).

Proof. Let d = diam(G) + 1 and P = [x1, x2, . . . , xd] be a diametral path in G. Let f
be a γhrs-function of P where s ∈ {2, 3}, and define the function g : V (G) → P({1, . . . , s})
by g(x) = f(x) for x ∈ V (P ) and g(x) = 1 for x ∈ V (G) \ V (P ). Clearly, g is an HsRD-
function of G of weight ω(f) + n − d − 1. This implies that γhrs(G) ≤ ω(f) + n − d − 1.
Thus, the corollary follows by Theorem 2.

Using Theorem 9 we obtain the next result.

Corollary 4. For every positive integer a, there exists a connected graph G such that
γhr2(G) = γr2(G) = a.

Proof. Clearly, γhr2(Ka) = γr2(Ka) = a for a ∈ {1, 2}. Assume that a ≥ 3. If a is odd
and a = 2m + 1, then by Theorems 8 and 9 we have that γhr2(C4m+1) = γr2(C4m+1) =
2m + 1 = a. Assume that a is even and let a = 2m for some m ≥ 2. Then again by
Theorems 8 and 9 we have γhr2(C4(m−1)+3) = γr2(C4(m−1)+3) = 2m = a.



J. J. Hamja et al. / Eur. J. Pure Appl. Math, 18 (2) (2025), 5973 13 of 17

Proposition 4. For any non-negative integer a, there is a connected graph G such that

γr2(G)− γhr2(G) = a.

Proof. Let G be the graph obtained from a star K1,a+4 by subdividing each edge
twice. It is not hard to see that γr2(G) = 2a + 8 and γhr2(G) = a + 8. Therefore,
γr2(G)− γhr2(G) = a.

Proposition 5. For any positive integer a, there is a connected graph G such that

γhr2(G)− γr2(G) = a.

Proof. Let G be the graph obtained from a star K1,a+1 by first subdividing each edge
twice and then adding a new pendant edge at each support vertex. It is easy to verify that
γhr2(G) = 2(a+ 1) + 2 and γr2(G) = a+ 4. Therfore, γhr2(G)− γr2(G) = a.

Remark 3. Let G be a connected graph. Then the hop k-rainbow domination and the
k-rainbow domination parameters are incomparable.

Proof. By Corollary 4, there exists a connected graph G such that γhr2(G) = γr2(G).
By Proposition 4, there exists a connected graph G′ such that γr2(G

′) > γhr2(G
′). Simi-

larly, by Proposition 5, there exists a connected graph G′′ such that γhr2(G
′′) > γr2(G

′′).
These results demonstrate that neither γr2(G) ≤ γhr2(G) nor γhr2(G) ≤ γr2(G) hold uni-
versally. Thus, γr2(G) and γhr2(G) are incomparable.

5. Graphs with γhr2(G) = n

In the next theorem we characterize all graphs G with γhr2(G) = n. For this purpose,
consider a family of graphs defined as follows.

Define F be the family of graphs G such that G can be constructed from a sequence
H0, H1, . . . ,Ht, (t ≥ 1), of graphs, where H0 is a complete graph as demonstrated in Figure
2 or H0 = K2 as demonstrated in Figure 3, G = Ht and, if t ≥ 1, then Hi+1 can be obtained
recursively from Hi by adding 2 new vertices and joining each of the new vertices to all
vertices in Hi.



J. J. Hamja et al. / Eur. J. Pure Appl. Math, 18 (2) (2025), 5973 14 of 17

H0 H1 H2

Figure 2: Example of graphs in the family F if H0 = K2

H1 H2H0

Figure 3: Example of graphs in the family F if H0 = K2

This family of graphs was introduced by Shabani et al. in [16] for characterizing the
graphs G of order n with γhR(G) = n (see Proposition 6).

In what follows is a useful result:

Proposition 6. [16] If G is a connected graph of order n, then γhR(G) = n if and only if
G ∈ F ∪ {P4}.

Theorem 10. Let k ≤ 2 be an integer and G be a connected graph of order n ≥ 1. Then
γhr2(G) = n if and only if G ∈ F ∪ {P4}.

Proof. Let G be a graph of order n ≥ 1 with γhr2(G) = n. We deduce from
n = γhr2(G) ≤ γhR(G) ≤ n that γhR(G) = n and Proposition 6 leads to G ∈ F ∪ {P4}.

Conversely, assume that G ∈ F ∪ {P4}. If G = P4, then clearly γhr2(G) = 4. Assume
that G ∈ F . By the construction of G we have δ(G) ≥ n− 2. Then by Proposition 4, we
have γhr2(G) = n.

6. Open questions and problems

We conclude this paper by mentioning some questions and problems suggested by this
research.

Using the construction introduced by Shabani et al. in [16], we characterize all con-
nected graph G of order n with γhr2(G) = n. Shabani et al. in [16], also characterize all
connected graph G of order n with γhR(G) = n−1. We think that using theirs construction
one can characterize all connected graph G of order n with γhr2(G) = n− 1.



J. J. Hamja et al. / Eur. J. Pure Appl. Math, 18 (2) (2025), 5973 15 of 17

Problem 1. Characterize all connected graphs G of order n such that γhr2(G) = n− 1.

Problem 2. For positive integer k ≥ 3, characterize the graphs G of order n such that
γhrk(G) = n.

In Theorem 3, we observed that for any positive integer k ≥ 2 and every graph G of
order n ≥ k+2 we have γhrk(G) ≥ k+1. To see the sharpness, let G be a graph obtained
from complete graph Kk+1 with vertex set v1, . . . , vk+1 by first adding r ≥ 0 new vertices
and connecting them to v1 and then adding s ≥ 0 new vertices and connecting them to
vk+1. Clearly assigning {1} to v1, vk+1, {i} to vertex vi for i ∈ {2, . . . , k} and ∅ to the
remaining vertices, if any, provides a hop k-rainbow dominating function on G of weight
k+1 and so γhrk(G) ≥ k+1. Thus, γhrk(G) = k+1. This example demonstrate that the
bound of Theorem 4 is sharp. Hence, we pose the following problem.

Problem 3. For positive integer k ≥ 2, characterize the graphs G of order n such that
γhrk(G) = k + 1.

Applying the bounds presented in Theorem 4, for any positive integer k ≥ 1 and every
graph G of order n, we have that

2min{n, k + 1} ≤ γhrk(G) + γhrk(G) ≤ 2n.

In particular, if n ≤ k + 1, then we have γhrk(G) + γhrk(G) ≤ 2n. So, finding Nordhaus-
Gaddum type results for graphs G of order n ≥ k + 2 is of interest.

Problem 4. For graphs G of order n ≥ k + 2, determine Nordhaus-Gaddum type results
for γhrk(G).

Problem 5. Design an algorithm for computing the value of γhrk(G) for any tree T and
k ≥ 3.

7. Conclusion

In this paper, we have introduced and analyzed the concept of hop k-rainbow domina-
tion in graphs. We established fundamental properties, derived bounds, and determined
exact values of γhrk(G) for several graph classes. Additionally, we identified graphs where
γhrk(G) = n and showed that the hop k-rainbow domination and the k-rainbow domination
parameters are incomparable. These results lay the groundwork for further exploration of
hop k-rainbow domination and its applications in graph theory.



J. J. Hamja et al. / Eur. J. Pure Appl. Math, 18 (2) (2025), 5973 16 of 17

Acknowledgements

The authors extend their heartfelt appreciation to the reviewers for their valuable com-
ments and suggestions, which have significantly improved the quality of this paper. They
are also deeply grateful for the financial support provided by the Department of Science
and Technology – Accelerated Science and Technology Human Resource Development Pro-
gram (DOST-ASTHRDP), Mindanao State University – Tawi-Tawi College of Technology
and Oceanography (MSU-TCTO), and Mindanao State University – Iligan Institute of
Technology (MSU-IIT), which made the publication of this work possible.

References

[1] T. W. Haynes, S. T. Hedetniemi, and M. A. Henning. Topics in domination in graphs,
volume 64 of Developments in Mathematics. Springer, Cham, 2020.

[2] B. Brešar, M. A. Henning, and D. F. Rall. Rainbow domination in graphs. Taiwanese
Journal of Mathematics, 12(1):213–225, 2008.

[3] Z. Shao, M. Liang, C. Yin, X. Xu, P. Pavlič, and J. Žerovnik. On rainbow domination
numbers of graphs. Information Sciences, 254:225–234, 2014.

[4] H. Abdollahzadeh Ahangar, J. Amjadi, N. Jafari Rad, and V. D. Samodivkin. Total
k-rainbow domination numbers in graphs. Communications in Combinatorics and
Optimization, 3(1):37–50, 2018.

[5] B. Brešar and T. K. Šumenjak. On the 2-rainbow domination in graphs. Discrete
Applied Mathematics, 155(17):2394–2400, 2007.

[6] B. Brešar and T.K. Šumenjak. On the 2-rainbow domination in graphs. Discrete
Applied Mathematics, 155:2394–2400, 2007.

[7] A. Mahmoodi and L. Volkmann. Outer-independent total 2-rainbow dominating func-
tions in graphs. Communications in Combinatorics and Optimization, 8(2):431–444,
2023.

[8] R. Y. Salkhori, E. Vatandoost, and A. Behtoei. 2-rainbow domination number of the
subdivision of graphs. Communications in Combinatorics and Optimization, 2023. In
press.

[9] Y. Wu and N. Jafari Rad. Bounds on the 2-rainbow domination number of graphs.
Graphs and Combinatorics, 29(4):1125–1133, 2013.

[10] C. Natarajan and S. K. Ayyaswamy. Hop domination in graphs II. Analele Ştiinţifice
ale Universităţii Ovidius Constanţa, Seria Matematică, 23(2):187–199, 2015.

[11] D. Anusha, J. John, and S. Joseph Robin. Graphs with small and large hop domination
numbers. Bulletin of the International Mathematical Virtual Institute, 11(3):483–489,
2021.

[12] D. Anusha, S. Joseph Robin, and J. John. Further results on the hop domination
number of a graph. Boletim da Sociedade Paranaense de Matemática, 42:1–12, 2024.

[13] S. K. Ayyaswamy, C. Natarajan, and G. Sathiamoorthy. A note on hop domination
number of some special families of graphs. International Journal of Pure and Applied
Mathematics, 119(12):11465–14171, 2018.



J. J. Hamja et al. / Eur. J. Pure Appl. Math, 18 (2) (2025), 5973 17 of 17

[14] A. E. Hassan, A. E. Gamorez, E. C. Ahmad, and J. J. Hamja. Certified hop domination
in graphs. International Journal of Mathematics and Computer Science, 19(4):1105–
1110, 2024.

[15] F. Harary. Graph theory. Addison-Wesley Publishing Company, Massachusetts, 1969.
[16] E. Shabani, N. Jafari Rad, and A. Poureidi. Graphs with large hop Roman domination

number. Computer Science Journal of Moldova, 27(1):3–22, 2019.
[17] E. J. Cockayne, P. M. Dreyer Jr., S. M. Hedetniemi, and S. T. Hedetniemi. On Roman

domination in graphs. Discrete Mathematics, 278(1-3):11–22, 2004.
[18] D. A. Mojdeh and Z. Mansouri. Rainbow domination of graphs. Transactions on

Combinatorics, 7(4):99–106, 2018. Presented at the 3rd International Conference on
Combinatorics.