EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS
Vol. 14, No. 3, 2021, 803-815
ISSN 1307-5543 – ejpam.com
Published by New York Business Global

Total Perfect Hop Domination in Graphs Under Some
Binary Operations

Raicah C. Rakim1,∗, Helen M. Rara1

1 Mathematics Department, College of Natural Sciences and Mathematics, Mindanao State
University-Main Campus, 9700 Marawi City, Philippines
2 Department of Mathematics and Statistics, College of Science and Mathematics, Center for
Graph Theory, Algebra, and Analysis, Premier Research Institute of Science and Mathematics,
Mindanao State University-Iligan Institute of Technology, 9200 Iligan City, Philippines

Abstract. Let G = (V (G), E(G)) be a simple graph. A set S ⊆ V (G) is a perfect hop dominating
set of G if for every v ∈ V (G) \ S, there is exactly one vertex u ∈ S such that dG(u, v) = 2.
The smallest cardinality of a perfect hop dominating set of G is called the perfect hop domination
number of G, denoted by γph(G). A perfect hop dominating set S ⊆ V (G) is called a total perfect
hop dominating set of G if for every v ∈ V (G), there is exactly one vertex u ∈ S such that
dG(u, v) = 2. The total perfect hop domination number of G, denoted by γtph(G), is the smallest
cardinality of a total perfect hop dominating set of G. Any total perfect hop dominating set of
G of cardinality γtph(G) is referred to as a γtph-set of G. In this paper, we characterize the total
perfect hop dominating sets in the join, corona and lexicographic product of graphs and determine
their corresponding total perfect hop domination number.

2020 Mathematics Subject Classifications: 05C76

Key Words and Phrases: total perfect hop domination, total perfect point-wise non-domination,
perfect total (1, 2)∗-domination, join, corona, lexicographic product

1. Introduction

Let G = (V (G), E(G)) be a simple graph. The open neighborhood of a vertex v
of G is the set NG(v) = {u ∈ V (G) : uv ∈ E(G)} and its closed neighborhood is the
set NG[v] = NG(v) ∪ {v}. The degree of v, denoted by degG(v), is equal to |NG(v)|.
The maximum degree of a graph G, denoted by ∆(G), is the maximum degG(u), for all
u ∈ V (G). Similarly, the minimum degree of a graph G, denoted by δ(G), is the minimum
degG(u), for all u ∈ V (G). If X ⊆ V (G), the open neighborhood of X in G is the set
NG(X) =

⋃
u∈X

NG(u). The closed neighborhood of X in G is the set NG[X] = NG(X)∪X.

∗Corresponding author.
DOI: https://doi.org/10.29020/nybg.ejpam.v14i3.3975

Email addresses: raicah.rakim@gmail.com (R. Rakim), helenrara@yahoo.com (H. Rara)

http://www.ejpam.com 803 © 2021 EJPAM All rights reserved.



R. Rakim, H. Rara / Eur. J. Pure Appl. Math, 14 (3) (2021), 803-815 804

A graph H = (V (H), E(H)) is a subgraph of a graph G = (V (G), E(G)) if V (H) ⊆
V (G) and E(H) ⊆ E(G). If C ⊆ V (G), then the induced subgraph 〈C〉 of G is the graph
with vertex set C and such that uv ∈ E(〈C〉) whenever u, v ∈ C and uv ∈ E(G).

Domination in graphs is one of the fastest growing research areas in Graph Theory.
Since then it has been an extensively investigated branch of graph theory. This is largely
due to a variety of new parameters that can be developed from the basic definition of
domination and its wide range of applications to other fields of study. Many authors
contribute several interesting domination parameters to nurture the growth of this research
area.

In 2015, Natarajan and Ayyaswamy [3] introduced a new domination parameter called
the hop domination number of a graph. In 2016, some variations of hop domination was
studied by Pabilona and Rara [4]. A subset S of V (G) is a hop dominating set of G if for
every v ∈ V (G) \ S, there exists u ∈ S such that dG(u, v) = 2. The smallest cardinality
of a hop dominating set of G, denoted by γh(G) is the hop domination number of G. A
hop dominating set S of G with cardinality γh(G) is called a γh-set of G. At the same
time of this year, Saromines and Rara [5] introduced a new hop domination parameter
called the perfect hop domination in graphs in which they characterized the perfect hop
dominating set of the join and corona of graphs. A subset S of V (G) is a perfect hop
dominating set of G if for every v ∈ V (G) \ S, there is exactly one vertex u ∈ S such that
dG(u, v) = 2. The smallest cardinality of a perfect hop dominating set of G, denoted by
γph(G)) is the perfect hop domination number of G. A perfect hop dominating set) S of
G with cardinality γph(G)) is called a γph-set) of G.

In 2018, Rara and Rakim present a further study on perfect hop dominaton in graphs
[5] and in the following year we also introduce connected perfect hop domination in graphs
under some binary operations [6].

A subset S of V (G) is a total hop dominating set [4] of G if for every v ∈ V (G), there
exists u ∈ S such that dG(u, v) = 2. The smallest cardinality of a total hop dominating
set of G, denoted by γth(G) is called the total hop domination number of G. Any total
hop dominating set of G with cardinality γth(G) is called a γth-set.

A set S ⊆ V (G) is a total point-wise non-dominating set [4] of G if for every v ∈ V (G),
there is a vertex u ∈ S such that v /∈ NG(u). The smallest cardinality of a total point-wise
non-dominating set of G, denoted by tpnd(G) is called the total point-wise non-domination
number of G. Any total point-wise non-dominating set S of G with |S| = tppnd(G) is
called a tpnd-set.

A set S ⊆ V (G) is a (1, 2)∗-dominating set [1] of G if for every w ∈ V (G) \ S, there
exists vertex x ∈ S such that wx ∈ E(G) and for every u ∈ V (G)\S, there is vertex v ∈ S
such that dG(u, v) = 2. The smallest cardinality of a (1, 2)∗-dominating set of G is called
the (1, 2)∗-domination number of G, denoted by γ∗1,2(G). A (1, 2)∗-dominating set S of G
with cardinality γ∗1,2(G) is called a γ∗1,2-set of G.

For other terms not define here, refer to [2].
In the next section, we introduce total perfect hop dominating set and explore some

of its properties.



R. Rakim, H. Rara / Eur. J. Pure Appl. Math, 14 (3) (2021), 803-815 805

2. Total Perfect Hop Dominating Set

Definition 2.1. A perfect hop dominating set S of V (G) is a total perfect hop dominating
set of G if for every v ∈ V (G), there is exactly one vertex u ∈ S such that dG(u, v) = 2.
The smallest cardinality of a total perfect hop dominating set of G, denoted by γtph(G) is
called the total perfect hop domination number of G. Any total perfect hop dominating set
of G with cardinality γtph(G)) is called a γtph-set.

Remark 2.2. Let G be a connected graph of order n ≥ 4. Then γtph(G) ≥ 4. Moreover,
for G = P4 or C4, V (G) is a total perfect hop dominating set of G. For n ≥ 6, V (G)
is a total perfect hop dominating set of G if and only if |V (G)| is even and the vertices
of G can be labeled u1, u2, ..., uV (G)

2

, v1, v2, ..., vV (G)
2

such that dG(ui, vi) = 2, dG(ui, uj) =

dG(vi, vj) = dG(ui, vj) = 1, whenever i 6= j.

Remark 2.3. Let G be a graph of order n. Then the total perfect hop dominating set of
G does not exist if γ(H) = 1.

Lemma 2.4. Let G be a connected graph of order n ≥ 4. Then S = {x1, x2, x3, x4} is a
total perfect hop dominating set of G if 〈S〉 ∼= P4 = [x1, x2, x3, x4] and for every v ∈ V (G)
at least one of the following holds.

(i) v ∈ NG(x1)\
⋃
i 6=1

NG(xi) and v /∈ NG(u) for each u ∈ NG(xj) where j = 3 or 4, or

(ii) v ∈ NG(x4)\
⋃
i 6=4

NG(xi) and v /∈ NG(u) for each u ∈ NG(xj) where j = 1 or 2, or

(iii) v ∈ [NG(x1) ∩NG(x2)]\
⋃

i=3,4

NG(xi) and v /∈ NG(u) for each u ∈ NG(x4), or

(iv) v ∈ [NG(x3) ∩NG(x4)]\
⋃

i=1,2

NG(xi) and v /∈ NG(u) for each u ∈ NG(x1), or

(v) v ∈
⋂
j

NG(xj) for exactly three xj’s, or

(vi) v ∈ NG(xk, 2)\
⋃
i 6=k

NG(xi) for k = 1 or 4 and degG(v) = 1, or

(vii) v ∈ NG(x1, 2)\
⋃
i 6=1

NG(xi) and v ∈ NG(u) for each u ∈ NG(x4, 2)\
⋃
j 6=4

NG(xj).

Proof. Suppose S = {x1, x2, x3, x4} and 〈S〉 ∼= P4 = [x1, x2, x3, x4]. Let
v ∈ V (G). If v ∈ S, then by Remark 2.2, |NG(v, 2) ∩ S| = 1. Suppose that v /∈ S.
If (i) and (ii) hold, then NG(v, 2) ∩ S = {xj} for j = 2 and j = 3, respectively. If (iii)
and (iv) hold, then NG(v, 2) ∩ S = {xk} for k = 3 and k = 2, respectively. For condition



R. Rakim, H. Rara / Eur. J. Pure Appl. Math, 14 (3) (2021), 803-815 806

(v), it can easily be verified that NG(v, 2) ∩ S = {xp} where p ∈ {1, 2, 3, 4}. If (vi) and
(vii) hold, then NG(v, 2) ∩ S = {xs} where s ∈ {1, 4}. Therefore S is a total perfect hop
dominating set of G. �

Lemma 2.5. Let G be a connected graph of order n ≥ 6. Then S = {x1, x2, x3, x4}
is a total perfect hop dominating set of G if 〈S〉 ∼= P2 ∪ K2 where P2 = [x2, x3] and
V (K2) = {x1, x4} and the following hold.

(i) |NG(x2) ∩NG(x4)| = 0 and |NG(x1) ∩NG(x2)| 6= 0

(ii) |NG(x1) ∩NG(x3)| = 0 and |NG(x3) ∩NG(x4)| 6= 0

(iii) For every v ∈ V (G), at least one of the following holds.

(a) v ∈ [NG(x1) ∩NG(u)]\
⋃
k 6=1

NG[xk] for each

u ∈ NG(x4)\
⋃
j 6=4

NG[xj ], or

(b) v ∈ NG(x2)\(NG[x3] ∪ NG[u]) or v ∈ NG(x3)\(NG[x2] ∪ NG[u]) for each u ∈
(NG(xi) ∩NG(xi+1)) where i ∈ {1, 3}, or

(c) v ∈ [NG(x2) ∩NG(u)]\
⋃
k 6=2

NG(xk) for each

u ∈ NG(x3)\
⋃
j 6=3

NG(xj), or

(d) v ∈ [NG(x2) ∩NG(x4)]\NG[x3], or

(e) v ∈ [NG(x1) ∩NG(x3)]\NG[x2], or

(f) v ∈ [NG(x2)∩NG(x3)∩NG(u)]\NG[xk] for each u ∈ [NG(xk)∩NG(xk+1)]\NG[x4]
if k = 1 or u ∈ [NG(xk) ∩NG(xk−1)]\NG[x1] if k = 4, or

(g) v ∈ [NG(x1) ∩ NG(x2) ∩ NG(u)]\[NG[x3] ∪ NG(w)] for each
u ∈ [NG(x1) ∩ NG(x2)]\NG[x4] and for each
w ∈ [NG(x3) ∩NG(x4)]\NG[x4], or

(h) v ∈ [NG(x3) ∩ NG(x4) ∩ NG(u)]\(NG[x2] ∪ NG[w]) for each
u ∈ [NG(x3) ∩ NG(x4)]\NG[x1] and for each
w ∈ NG(x1) ∩NG(x2), or

(i) v ∈ [NG(x1)∩NG(u)]\[(
⋃

k 6=1NG(xk))∪NG(w)] for each u ∈ NG(x1)∩NG(x2)
and for each w ∈ NG(x4), or

(j) v ∈ [NG(x4)∩NG(u)]\[(
⋃

k 6=4NG(xk))∪NG(w)] for each u ∈ NG(x3)∩NG(x4),
and for each w ∈ NG(x1), or

(k) v satisfies condition (f) and v ∈ NG(w) for

w ∈ NG(x2)\
⋃
k 6=2

NG(xk), or

(l) v satisfies condition (i) and v ∈ NG(w) where degG(w) = 1, or



R. Rakim, H. Rara / Eur. J. Pure Appl. Math, 14 (3) (2021), 803-815 807

(m) v satisfies condition (j) and v ∈ NG(w) where degG(w) = 1, or

(n) v satisfies condition (c) and v ∈ NG(w) and u ∈ NG(y) where degG(w) =
degG(y) = 1.

Proof. Suppoose S = {x1, x2, x3, x4} and 〈S〉 ∼= P2∪K2 where P2 = [x2, x3] and V (K2) =
{x1, x4}. Let v ∈ V (G). If v ∈ S, then by (i) and (ii), |NG(v, 2) ∩ S| = 1. Suppose that
v /∈ S. If (iii)(a) holds, then NG(v, 2) ∩ S = {x4}. If (iii)(b) holds, then NG(v, 2) ∩
S = {x3} for v ∈ NG(x2) and NG(v, 2) ∩ S = {x2} for v ∈ NG(x3). If (iii)(c) holds,
then NG(v, 2) ∩ S = {x3}. If (iii)(d) and (iii)(e) hold, then NG(v, 2) ∩ S = {x3} for
v ∈ NG(x2) ∩ NG(x4) or NG(v, 2) ∩ S = {x2} for v ∈ NG(x1) ∩ NG(x3). If (iii)(f) holds,
then NG(v, 2) ∩ S = {x1} for v ∈ NG(x2) ∩ NG(x3) ∩ NG(u) and u ∈ NG(x1) ∩ NG(x2)
or NG(v, 2) ∩ S = {x4} for v ∈ NG(x2) ∩ NG(x3) ∩ NG(u) and u ∈ NG(x3) ∩ NG(x4). If
(iii)(g) and (iii)(h) hold, then NG(v, 2) ∩ S = {x3} for v ∈ NG(x1) ∩ NG(x2) ∩ NG(u) or
NG(v, 2) ∩ S = {x2} for v ∈ NG(x3) ∩ NG(x4) ∩ NG(u). If (iii)((i) and (j)) hold, then
NG(v, 2)∩S = {x2} for v ∈ NG(x1)∩NG(u) or NG(v, 2)∩S = {x3} for v ∈ NG(x4)∩NG(u).
If (k) holds, then NG(w, 2) ∩ S = {x2} for w ∈ NG(v) ∩NG(x3) or NG(w, 2) ∩ S = {x3}
for w ∈ NG(v) ∩ NG(x2). If (l) holds, then NG(w, 2) ∩ S = {x1}. If (m) holds, then
NG(w, 2) ∩ S = {x4}. If (n) holds, then NG(w, 2) ∩ S = {x2}. Therefore, S is a total
perfect hop dominating set of G. �

Lemma 2.6. Let G be a graph of order n ≥ 4. Then S = {x1, x2, x3, x4} is not a total
perfect hop dominating set of G if the following hold.

(i) 〈S〉 ∼= K2 ∪K2 where x1x2, x3x4 ∈ E(G).

(ii) 〈S〉 ∼= P3 ∪K1.

(iii) 〈S〉 ∼= K4.

Proof. If (i) holds and S = {x1, x2, x3, x4} is a total perfect hop dominating set of G, then
there exists v ∈

⋂
j NG(xj) for j = 1, 2, 3 since NG(x1, 2)∩ S 6= ∅ and NG(x2, 2)∩ S 6= ∅.

Hence, dG(x3, x1) = dG(x3, x2) = 2 contrary to our assumption that S is a total perfect
hop dominating set of G. Similarly, there exists u ∈

⋂
kNG(xk) for k = 2, 3, 4 since

NG(x3, 2) ∩ S 6= ∅ and NG(x4, 2) ∩ S 6= ∅. Hence, dG(x2, x3) = dG(x2, x4) = 2 is
a contradiction to our assumption that S is a total perfect hop dominating set of G.
Similarly, if (ii) and (iii) hold, then S is not a perfect hop dominating set of G. �

Theorem 2.7. Let G be a connected graph of order greater than 3. Then γtph(G) = 4 if
and only if G = P4 or G = C4 or |V (G)| ≥ 5 and there exist vertices x1, x2, x3, x4 of G
such that 〈{x1, x2, x3, x4}〉 ∼= P4 or 〈{x1, x2, x3, x4}〉 ∼= P2 ∪K2 and the conditions given
in Lemma 2.4 and Lemma 2.5 are satisfied.

Proof. Let γtph(G) = 4. If |V (G)| = 4, then G4 or C4. Suppose that
|V (G)| ≥ 6 and S = {x1, x2, x3, x4} be a γtph-set. Suppose that 〈{x1, x2, x3, x4}〉 � P4 or
〈{x1, x2, x3, x4}〉 � P2 ∪K2. Then either 〈S〉 ∼= [x1, x2]∪ [x3, x4] or 〈S〉 ∼= [x1, x2, x3]∪K1



R. Rakim, H. Rara / Eur. J. Pure Appl. Math, 14 (3) (2021), 803-815 808

where V (K1) = {x4} or 〈S〉 ∼= K4 where V (K4) = {x1, x2, x3, x4}. Thus, by Lemma 2.6,
S is not a total perfect hop dominating set of G contrary to our assumption.

The converse follows immediately from Lemmas 2.4 and 2.5. �

Corollary 2.8. Let n, s, and r be positive integers with r ≥ 0.

(i) γtph(Pn) = 4r + 4 if n = 8r + s; 4 ≤ s ≤ 8

(ii) γtph(Cn) =

{
4, if n = 4

4r + 4, if n = 8r + 8.

Definition 2.9. A set S ⊆ V (G) is a total perfect point-wise non-dominating set of G
if for every v ∈ V (G), there is exactly one vertex u ∈ S such that v /∈ NG(u). The
smallest cardinality of a total perfect point-wise non-dominating set of G, denoted by
tppnd(G) is called the total perfect point-wise non-domination number of G. Any total
perfect point-wise non-dominating set S of G with |S| = tppnd(G) is called a tppnd-set.

Remark 2.10. Let G be a graph of order n. Then the total perfect point-wise non-dominating
set of G does not exist if γ(H) = 1.

Remark 2.11. Let G be a graph of order n ≥ 4. Then tppnd(G) ≥ 2.

Theorem 2.12. Let G be a connected graph of order n ≥ 4. Then tppnd(G) = 2 if only
if there exist non-adjacent vertices x, y ∈ V (G) such that V (G)\{x, y} = NG(x) ∪NG(y)
and NG(y) ∩NG(x) = ∅.

Proof. Suppose tppnd(G) = 2. Let S = {x, y} be a tppnd-set of G. Let z ∈ V (G)\{x, y}.
Since S is a total perfect point-wise non-dominating set of G, z /∈ NG(x) or z /∈ NG(y)
but not both. Hence, NG(x) ∪NG(y) and NG(y) ∩NG(x) = ∅.

Conversely, suppose that there exist non-adjacent vertices x, y ∈ V (G) satisfying the
given condition. Let S = {x, y} and let u ∈ V (G). Then either u ∈ NG(x)\NG(y) or
u ∈ NG(y)\NG(x). It follows that S is a total perfect point-wise non-dominating set of
G. By Remark 2.11, tppnd(G) = 2. �

Corollary 2.13. Let n ≥ 4 be a positive integer.

(i) tppnd(Pn) = 2 if 4 ≤ n ≤ 6

(ii) tppnd(Cn) = 2 if n = 4, 6.

Remark 2.14. Let G be a graph of order n ≥ 4. If S is a tppnd-set of G, then |S| is
even.



R. Rakim, H. Rara / Eur. J. Pure Appl. Math, 14 (3) (2021), 803-815 809

3. Join of Graphs

The join G + H of two graphs G and H is the graph with vertex set V (G + H) =
V (G) ∪ V (H) and edge-set E(G+H) = E(G) ∪ E(H) ∪ {uv : u ∈ V (G) and v ∈ V (H)}.

Theorem 3.1. Let G and H be graphs with ∆(G) 6= |V (G)| − 1 and
∆(H) 6= |V (H)| − 1. A subset S of V (G + H) is a total perfect hop dominating set
of G + H if and only if S = SG ∪ SH , where SG and SH are total perfect point-wise
non-dominating sets of G and H, respectively.

Proof. Suppose that S ⊆ V (G+H) is a total perfect hop dominating set of G+H. Let
SG = S ∩ V (G) and SH = S ∩ V (H). If SG = ∅ , then S = SH . Since V (G) ⊆ NG+H(S),
S is not a total perfect hop dominating set of G+H, a contradiction to our assumption.
Thus, SG 6= ∅. Similarly, SH 6= ∅. Let v ∈ V (G). Then there exists a unique vertex
y ∈ S such that dG+H(y, v) = 2. So that y ∈ SG and v /∈ NG(y). Hence, SG is a total
perfect point-wise non-dominating set of G. Similarly, SH is a total perfect point-wise
non-dominating set of H.

Conversely, suppose S = SG ∪ SH , where SG and SH are total perfect point-wise
non-dominating sets of G and H, respectively. Let v ∈ V (G + H). If v ∈ V (G), then
there exists a unique vertex z ∈ SG such that v /∈ NG(z). Hence, by definition of G+H,
dG+H(z, v) = 2. Similarly, if v ∈ V (H), then there exists a unique vertex z∗ ∈ SH such
that dG+H(z∗, v) = 2. Therefore, S is a total perfect hop dominating set of G+H. �

The next result follows immediately from Theorem 3.1

Corollary 3.2. Let G and H be graphs with ∆(G) 6= |V (G)| − 1 and
∆(H) 6= |V (H)| − 1. Then, γtph(G+H) = tppnd(G) + tppnd(H). In particular,

(i) γtph(Pn + Pm) = 4 if 4 ≤ m,n ≤ 6

(ii) γtph(Cn + Cm) = 4 if n,m = 4, 6.

4. Corona of Graphs

The corona G ◦H of two graphs G and H is the graph obtained by taking one copy
of G of order n and n copies of H, and then joining the ith vertex of G to every vertex in
the ith copy of H. For every v ∈ V (G), denote by Hv the copy of H whose vertices are
attached one by one to the vertex v. Subsequently, denote by v+Hv the subgraph of the
corona G ◦H corresponding to the join 〈v〉+Hv = v +Hv.

Definition 4.1. A set S ⊆ V (G) is a perfect total (1, 2)∗-dominating set of G if for
every w ∈ V (G), there is exactly one vertex x ∈ S such that wx ∈ E(G) and for every u ∈
V (G)\S, there is exactly one vertex v ∈ S such that dG(u, v) = 2. The smallest cardinality
of a perfect total (1, 2)∗-dominating set of G is called the perfect total (1, 2)∗-domination
number of G, denoted by γ∗pt1,2 (G). A perfect total (1, 2)∗-dominating set S of G with

cardinality γ∗pt1,2 (G) is called a γ∗pt1,2 -set of G.



R. Rakim, H. Rara / Eur. J. Pure Appl. Math, 14 (3) (2021), 803-815 810

Theorem 4.2. Let G be a connected nontrivial graph whose perfect total (1, 2)∗-dominating
set exists and H a graph with γ(H) = 1. Then G ◦H has a total perfect hop dominating

set S if and only if S = A ∪ (
⋃

v∈V (G)

Sv) where Sv ⊆ V (Hv) for every v ∈ V (G) and the

following conditions are satisfied.

(i) A ⊆ V (G) is a perfect total (1, 2)∗-dominating set of G.

(ii) For each v ∈ V (G)\A, Su = ∅ for all u ∈ NG(v).

(iii) For each v ∈ A, NG(v, 2) ∩ S = ∅ and Sw is a γ-set of H for a unique w ∈
V (G) ∩NG(v).

Proof. Suppose S is a total perfect hop dominating set of G◦H and A = V (G)∩S. Then
A ⊆ V (G). Also, S is a perfect hop dominating set of G ◦ H. Let x ∈ V (G). If x /∈ A,
then x /∈ C. Hence, there exists a unique vertex v ∈ C such that dG◦H(x, v) = 2. We
claim that v ∈ A. Suppose that v /∈ A. Then there exists a vertex w ∈ V (G) such that
v ∈ V (Hw) and xw ∈ E(G). If |V (G)| = 2, then H is a trivial graph or v is an isolated
vertex of H, which is a contradiction to the hypothesis. If |V (G)| > 2, then there exist
vertices a ∈ NHw(v) \ C and b ∈ A such that dG◦H(a, b) = 2. Thus, wb ∈ E(G) implying
that dG◦H(x, b) = 2 . This is a contradiction since C is a perfect hop dominating set of
G ◦H and dG◦H(x, v) = 2 = dG◦H(x, b) where v, b ∈ C. Hence, v ∈ A. This implies that
A is a perfect hop dominating set of G. We claim that A is a perfect total dominating set
of G. Let v ∈ V (G) and a ∈ V (Hv) such that degHv(a) = |V (H)| − 1. Since S is a total
perfect hop dominating set of G ◦H, a unique vertex u ∈ NG(v) ∩ S exists. Thus, u ∈ A
implying that A is a perfect total dominating set of G. Hence, (i) holds. Let v ∈ V (G)\A.
By (i), there exists a unique vertex w ∈ NG(v, 2) ∩ A. Suppose that Su 6= ∅ for some
u ∈ NG(v). Then there exists a ∈ Su and a ∈ NG◦H(v, 2)∩ S, contrary to our assumption
that S is a total perfect hop dominating set of G ◦H. Thus, Su = ∅ and (ii) holds. For
(iii), let v ∈ A. If a ∈ NG(v, 2) ∩ S, then there exists b ∈ NG(v) ∩ NG(a). This implies
that for all x ∈ V (Hb), x ∈ NG(v, 2) ∩NG(a, 2), a contradiction to our assumption for S.
Thus, NG(v, 2) ∩ S = ∅. Since S is a total perfect hop dominating set of G ◦ H, there
exists a unique vertex u ∈ S ∩NG◦H(v, 2). Since NG(v, 2) ∩ S = ∅, u ∈ V (Hw) ∩ S = Sw
for a unique w ∈ V (G) ∩NG(v). Since γ(H) = 1, Sw is γ-set of H.

Conversely, suppose that S = A ∪ (
⋃

v∈V (G)\A

Sv) satisfying conditions (i),(ii) and (iii).

Let v ∈ V (G◦H). Suppose that v ∈ V (G)\A. Then by (i) and (ii), we are done. If v ∈ A,
then by (iii) there exists a unique w ∈ NG(v)∩V (G) such that Sw is a γ-set of H. Hence,
there exists a vertex a ∈ Sw ∩NG(v, 2). Suppose v ∈ V (Hw) for w ∈ V (G). By (i), there
exists a unique vertex u ∈ NG(w) ∩ A. Hence, u ∈ NG◦H(v, 2). Therefore S is a total
perfect hop dominating set of G ◦H. �

Corollary 4.3. Let G be a connected graph of order n ≥ 4 whose perfect total (1, 2)∗-dominating
set exists and H a graph with γ(H) = 1. Then γtph(G ◦H) ≤ γ∗pt1,2 (G)+n.



R. Rakim, H. Rara / Eur. J. Pure Appl. Math, 14 (3) (2021), 803-815 811

Proof. Let S = A∪ (
⋃

v∈V (G)

Sv) be a minimum total perfect hop dominating set of G ◦H.

By Theorem 4.2, A is a γ∗pt1,2 -set of G and (ii) and (iii) hold. Then γtph(G ◦ H) = |C| =

|A|+
∑

v∈V (G)

|Sv| ≤ |A|+ V (G) = γ∗pt1,2 (G) + n. �

The next result shows that the bound given in Corollary 4.3 is sharp.

Corollary 4.4. Let H be a graph with γ(H) = 1. Then the total perfect hop dominating
set of P2 ◦H exists and γtph(P2 ◦H) = 4.

Proof. Let P2 = [x1, x2]. By Theorem 4.2, S = {x1, x2, a, b}, where
a ∈ V (Hx1), b ∈ V (Hx2) and degH(a) = degH(b) = |V (H)| − 1 is a total perfect hop
dominating set of P2 ◦H. Thus, by Remark 2.2, γtph(P2 ◦H) = |S| = 4. �

Remark 4.5. The strict inequality in Corollary 4.3 can be attained.

To illustrate Remark 4.5, consider the graph P4 ◦ P3. It can be verified that γtph(P4 ◦
P3) = 4. However, γ∗pt1,2 (G) + |V (G)| = 2 + 4 = 6. Hence, strict inequality is attained.

Corollary 4.6. Let G be a connected graph of order 3 and H be a graph with γ(H) = 1.
Then the total perfect hop dominating set of G ◦H does not exist.

Proof. If |V (G)| = 3, then G ∼= P3 or G ∼= K3. Hence, Theorem 4.2 is not satisfied.
Therefore, the total perfect hop dominating set of G ◦H does not exist. �

If G is a complete graph Kn, then G has no total perfect hop dominating set. Thus,
the next result follows immediately from Theorem 4.2.

Corollary 4.7. Let n ≥ 3 and H a graph with γ(H) = 1. Then the total perfect hop
dominating set of Kn ◦H does not exist.

Corollary 4.8. Let H be a connected graph with γ(H) = 1. Then the total perfect hop
dominating set of Cn ◦H for n ≥ 3 does not exist.

Proof. Note that if n 6≡ 0 (mod 4), then Cn does not have a total perfect hop dominating
set. If Cn has a total perfect hop dominating set A, then every vertex outside A hops in
A and so none of the element in A hops in A. Thus, (iii) in Theorem 4.2 is never satisfied.
�

Corollary 4.9. Let G be a connected graph of order 4 and H be any graph with γ(H) = 1.
Then the total perfect hop dominating set of G ◦H exists if and only if G ∼= P4.

Proof. If G ∼= P4 = [x1, x2, x3, x4], then S = {x2, x3, a, b} where a ∈ V (Hx1), b ∈ V (Hx4)
and degH(a) = degH(b) = |V (H)| − 1 is a total perfect hop dominating set of G ◦ H.
If G ∼= C4 or G ∼= K4, then by Corollary 4.8 or Corollary 4.7, respectively, the total
perfect hop dominating set of G ◦H does not exist. Suppose G /∈ {P4, C4,K4}. Then G is
isomorphic to one of the graphs shown in figure below. By Theorem 4.2 below, it can be
verified that the total perfect hop dominating set of G ◦H where G is one of the graphs
shown below does not exist.



R. Rakim, H. Rara / Eur. J. Pure Appl. Math, 14 (3) (2021), 803-815 812

Therefore the corollary follows. �

Theorem 4.10. Let H be a graph with γ(H) = 1. Then the total perfect hop dominating
set of Pn ◦H exists if and only if n = 2 and n = 4. Moreover, γtph(Pn ◦H) = 4.

Proof. By Corollary 4.4 and Corollary 4.9, P2 ◦ H and P4 ◦ H both have total perfect
hop dominating set. Let Pn = [x1, x2, ..., xn]. Suppose n 6= 2 and n 6= 4. By Corollary
4.6, P3 ◦ H does not exist. Let n > 4 and assume that Pn ◦ H has a total perfect hop
dominating set S. By Theorem 4.2(i), x2 ∈ S and x1 ∈ S or x3 ∈ S but not both. Suppose
x1 ∈ S. Since x3 /∈ S, by Theorem 4.2(iii), V (Hx1) ∩ S 6= ∅. Let y ∈ V (Hx2) ∩ S. Then
y ∈ NPn◦H(x3, 2) ∩ S and x1 ∈ NPn◦H(x3, 2) ∩ S, contrary to our assumption that S is a
total perfect hop dominating set of Pn ◦ H. Suppose x3 ∈ S and x1 /∈ S. By Theorem
4.2(i), x4 /∈ S. This implies that e /∈ S for all e ∈ V (Hx3). Thus, c ∈ S for a unique
vertex c ∈ V (Hx1) where degH(c) = |V (H)| − 1. Again by Theorem 4.2(i), x1 /∈ S and
x5 /∈ S. Hence, by Theorem 4.2(ii), |V (Hx4 ∩ S)| = 1. Let y ∈ V (Hx4) ∩ S. Then
dPn◦H(x5, x3) = dPn◦H(x5, y) = 2, contrary to our assumption that S is a total perfect
hop dominating set of Pn ◦H. Thus, the total perfect hop dominating set of Pn ◦H for
n > 4 does not exist. Therefore, the total perfect hop dominating set of Pn ◦H exists if
and only if n = 2 and n = 4. Clearly, γtph(Pn ◦H) = 4 for n = 2 and n = 4. �

Theorem 4.11. Let G be a non-complete graph with |V (G)| ≥ 3 and
γ(G) = 1 and H a graph with γ(H) = 1. Then the total perfect hop dominating set
of G ◦H does not exist.

Proof. Suppose that G ◦ H has a total perfect hop dominating set S. Let
y ∈ V (G) with degG(y) = |V (G)| − 1. By Theorem 4.2(i), there exists a unique vertex
x ∈ V (G) ∩ S. If degG(z) = |V (H)| − 1, y ∈ S. If there exists a unique vertex z ∈
NG(x, 2)∩S, then dG◦H(a, z) = dG◦H(a, x) = 2 for a ∈ V (Hy). If there exists a unique a ∈
V (Hy)∩S. Then dG◦H(z, a) = dG◦H(z, x) = 2 where z ∈ V (G)\{x}. Suppose degG(x) ≥ 2.
Let u, v ∈ NG(x) with u 6= v. By Theorem 4.2(i), there exists a unique vertex z ∈
V (G) ∩NG(x) ∩ S. If z = y = u 6= v, then dG◦H(b, y) = dG◦H(b, x) = 2 for all b ∈ V (Hv).
If z = v 6= y, then dG◦H(b, v) = dG◦H(b, x) = 2 for all b ∈ V (Hy). This implies that
S is not a total perfect hop dominating set of G ◦ H. Therefore, the total perfect hop
dominating set of G ◦H does not exist. �

5. Lexicographic Product

The lexicographic product of two graphs G and H, denoted by G[H], is the graph with
V (G[H]) = V (G)×V (H) and (u1, u2)(v1, v2) ∈ E(G[H]) if either u1v1 ∈ E(G) or u1 = v1
and u2v2 ∈ E(H).



R. Rakim, H. Rara / Eur. J. Pure Appl. Math, 14 (3) (2021), 803-815 813

Theorem 5.1. Let G be a nontrivial complete graph and H a nontrivial connected non-complete

graph whose total perfect point-wise non-dominating set exists. A subset C =
⋃
x∈S

[{x}×Tx]

of V (G[H]) where S ⊆ V (G) and Tx ⊆ V (H) for each x ∈ S, is a total perfect hop
dominating set of G[H] if and only if S = V (G) and Tx is a total perfect point-wise
non-dominating set of H for each x ∈ S.

Proof. Let C =
⋃
x∈S

[{x} × Tx] where S ⊆ V (G) and Tx ⊆ V (H) for each x ∈ S be a

total perfect hop dominating set of G[H]. Then C is a perfect hop dominating set of
G[H]. Suppose S 6= V (G). Let u ∈ V (G)\S. Then (u, a) /∈ C for any a ∈ V (H). Thus,
there exists a unique vertex (y, b) ∈ C such that dG[H]((u, a), (y, b)) = 2. Since u /∈ S
and y ∈ S, u 6= y and dG(u, y) = 2. This implies that (y, p) /∈ C for all p ∈ V (H)\{b}.
Since γ(H) 6= 1, choose q ∈ V (H)\{b} such that q /∈ NH(b). Then dG[H]((y, q), (y, b)) = 2.
Pick any t ∈ NH(b). Then there exists z ∈ S\{y} such that dG(y, z) = 2. Let r ∈
Tz. Then dG[H]((y, q), (z, r)) = 2, a contradiction to the fact that C is a perfect hop
dominating set of G[H]. Therefore S = V (G). Let x ∈ S. Suppose that NG(x, 2) 6= ∅
and Tx 6= V (H). Let z ∈ NG(x, 2), p ∈ Tz and a ∈ V (H)\Tx. Since (x, a) /∈ C,
there is exactly one vertex (y, b) ∈ C such that dG[H]((x, a), (y, b)) = 2. This implies
that x = y and ab /∈ E(H) or dG(x, y) = 2. Suppose x = y and ab /∈ E(G). Then
dG[H]((x, a), (y, b)) = dG[H]((x, a), (z, p)) = 2 contrary to our assumption that C is a
perfect hop dominating set of G[H]. On the other hand, suppose that dG(x, y) = 2. If
y 6= z, then dG[H]((x, a), (y, b)) = dG[H]((x, a), (z, p)) = 2. If y = z, then b = p. Since
γ(H) 6= 1, there exists q ∈ V (H)\NH [p]. Let w ∈ Tx. Then dG[H]((z, q), (z, p)) =
dG[H]((z, q), (x,w)) = 2. Since (z, q) /∈ C because |Tx| = 1, it follows that C is not a
perfect hop dominating set of G[H] a contradiction to our assumption for C. Therefore
Tx = V (H). Now, let NG(x, 2) = ∅ and a ∈ V (H)\Tx. Then (x, a) /∈ C and it follows that
there is a unique vertex (y, b) ∈ C such that dG[H]((x, a), (y, b)) = 2. Since NG(x, 2) = ∅,
x = y and ab /∈ E(H). This implies that Tx is a perfect point-wise non-dominating set of
H. Therefore Tx is a perfect point-wise non-dominating set of H for all x ∈ S. We claim
that Tx is a total perfect point-wise non-dominating set of H for all x ∈ S. Let x ∈ S and
c ∈ Tx. Then (x, c) ∈ C. Since C is a total perfect hop dominating set of G[H], there is
a unique vertex (y, d) ∈ C such that dG[H]((x, c), (y, d)) = 2. Since G is complete, x = y
and cd /∈ E(G) This implies that d ∈ Tx and cd /∈ E(H). Therefore, Tx is a total perfect
point-wise non-dominating set of H.

Conversely, let S = V (G) and Tx be a total perfect point-wise non-dominating set
of H for all x ∈ S. Since every total perfect point-wise non-dominating set is a perfect
point-wise non-dominating set, Tx is a perfect point-wise non-dominating set of H for all
x ∈ S. Let (x, a) /∈ C. Since S = V (G), a /∈ Tx. If NG(x, 2) 6= ∅, then we are done
since Tx = V (H). If NG(x, 2) = ∅, then there exists a unique vertex b ∈ Tx such that
ab /∈ E(H). Thus, (x, b) ∈ C and dG[H]((x, a), (x, b)) = 2. Accordingly, C is a perfect hop
dominating set of G[H]. Let (x, a) ∈ C. Then x ∈ S and a ∈ Tx. Since Tx is a total
perfect point-wise non-dominating set of H, there is a unique vertex b ∈ Tx such that
ab /∈ E(H). Since G is a nontrivial complete graph, there exists y ∈ V (G)∩NG(x). Thus,



R. Rakim, H. Rara / Eur. J. Pure Appl. Math, 14 (3) (2021), 803-815 814

dG[H]((x, a), (x, b)) = dG[H]((x, a), (y, a)) + dG[H]((y, a), (x, b)) = 1 + 1 = 2.

Since b is unique, (x, b) is a unique vertex in C. Therefore C is a total perfect hop
dominating set of G[H]. �

Corollary 5.2. Let G be a nontrivial complete graph and H a nontrivial connected
non-complete graph whose total perfect point-wise non-dominating set exists. Then γtph(G[H]) =
|V (G)| · tppnd(H).

Proof. Let C =
⋃
x∈S

[{x} × Tx] be a minimum total perfect hop dominating set of G[H].

By Theorem 5.1, S = V (G) and Tx is a minimum total perfect point-wise non-dominating
set of H for all x ∈ S. Therefore γtph(G[H]) = |C| =

∑
x∈V (G) |Tx| = |V (G)| · tppnd(H) �

Theorem 5.3. Let G be a nontrivial connected graph whose total perfect hop dominating
set exists and H a nontrivial connected graph with γ(H) = 1. Then a nonempty subset

C =
⋃
x∈S

[{x} × Tx] of V (G[H]) where S ⊆ V (G) and Tx ⊆ V (H) for all x ∈ S, is a total

perfect hop dominating set of G[H] if and only if S is a total perfect hop dominating set
of G and Tx is a γ-set of H.

Proof. Let C =
⋃
x∈S

[{x} × Tx], where S ⊆ V (G) and Tx ⊆ V (H) for all x ∈ S, be a total

perfect hop dominating set of G[H]. Then C is a perfect hop dominating set of G[H].
We claim that S is a total perfect hop dominating set of G. Let u ∈ V (G). If u /∈ S,
then (u, a) /∈ C for any a ∈ V (H). Thus, there is exactly one vertex (v, b) ∈ C such that
dG[H]((u, a), (v, b)) = 2. Since u /∈ S and v ∈ S, u 6= v and dG(u, v) = 2. Suppose u ∈ S.
Since G has a total perfect hop dominating set, NG(u, 2) 6= ∅. Let z ∈ NG(u, 2). If z ∈ S,
then we are done. So suppose that z /∈ S. Then |Tu| = 1, say Tu = {p} for some p ∈ V (H)
because C is a perfect hop dominating set of G[H]. Let a ∈ NH(p). Then there exists
a unique (w, b) ∈ C ∩ NG[H]((u, a), 2). Since b 6= p, u 6= w. Thus, w ∈ S ∩ NG(u, 2).
Hence, NG(u, 2) ∩ S 6= ∅. Therefore S is a total perfect hop dominating set of G. Now,
let x ∈ S. Since S is a total perfect hop dominating set of G, |Tx| = 1, say Tx = {a}.
Let p ∈ V (H)\Tx. Suppose p /∈ NH(a). Then dG[H]((x, p), (x, a)) = 2. Since S is a total
perfect hop dominating set of G, there exists a unique y ∈ NG(x, 2)∩ S. Pick any c ∈ Ty.
Then (y, c) 6= (x, a) but dG[H]((x, p), (y, c)) = 2. This implies that C is not a perfect hop
dominating set of G[H], a contradiction. Therefore, Tx is a γ-set of H.

Conversely, let S be a total perfect hop dominating set of G and Tx is a γ-set of H
for every x ∈ S. Let (x, a) /∈ C. Then either x /∈ S or x ∈ S and a /∈ Tx. If x /∈ S,
then a unique vertex y ∈ S exists such that dG(x, y) = 2. Since Ty is a γ-set of H for
every y ∈ S, a unique vertex b ∈ Ty exists such that for all p ∈ V (H)\{b}, p ∈ NH(b).
Then (y, b) ∈ C and dG[H]((x, a), (y, b)) = 2. Suppose x ∈ S and a /∈ Tx. Then there
is exactly one vertex z ∈ S such that dG(x, z) = 2. Since Tz is a γ-set of H for every
z ∈ S, a unique vertex c ∈ Tz exists. Hence, (z, c) ∈ C and dG[H]((x, a), (z, c)) = 2.
Therefore C is a perfect hop dominating set of G[H]. Let (x, a) ∈ C. Since x ∈ S and S



REFERENCES 815

is a total perfect hop dominating set of G, there exists a unique vertex y ∈ S such that
dG(x, y) = 2. Since Ty is a γ-set of H and γ(H) = 1, there exists b ∈ Ty. Hence, (y, b) ∈ C
and dG[H]((x, a), (y, b)) = 2. Therefore C is a total perfect hop dominating set of G[H]. �

Corollary 5.4. Let G be a nontrivial connected graph whose total perfect hop dominating
set exists and H a nontrivial connected graphs with γ(H) = 1. Then γtph(G[H]) = γtph(G).

Proof. Let C =
⋃
x∈S

[{x} × Tx] be a minimum connected perfect hop dominating set of

G[H]. Then by Theorem 5.3, S is a minimum total perfect hop dominating set of G and
Tx = {a} where a ∈ V (H) such that degH(a) = |V (H)|−1. Therefore γtph(G[H]) = |C| =
|S| = γtph(G). �

References

[1] S Arriola and S Canoy. (1; 2)∗ -domination in graphs. The Asian Mathematical
Conference, 2016.

[2] F Harary. Graph Theory. Addisson-Wesley Publishing Company, 1969.

[3] C Natarajan and S K Ayyaswamy. Hop Domination in Graphs II. Versita,
23(2):187–199, 2015.

[4] Y Pabilona and H Rara. Total Hop Dominating Set in the join, corona, and
lexicographic product of graphs. Journal of Algebra and Applied Mathematics, 2017.

[5] C Saromines R Rakim and H Rara. Perfect Hop Domination in Graphs. Applied
Mathematical Sciences, 12:635–649, 2018.

[6] Y Pabilona R Rakim and H Rara. Connected Perfect Hop Domination in Graphs
under some binary operations. Advances and Applications in Discrete Mathematics,
20, 2019.