EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS Vol. 14, No. 4, 2021, 1415-1428 ISSN 1307-5543 – ejpam.com Published by New York Business Global Revisiting Domination, Hop Domination, and Global Hop Domination in Graphs Gemma Salasalan1,∗, Sergio R. Canoy, Jr.2,3 1 Department of Arts and Sciences, Institute of Teacher Education, Arts and Sciences, Davao del Sur State College, Matti, Digos City, Davao del Sur, Philippines 2 Department of Mathematics and Statistics, College of Science and Mathematics, MSU-Iligan Institute of Technology, , 9200 Iligan City, Philippines 3 Center of Graph Theory, Algebra and Analysis, Premier Research Institute of Science and Mathematics, MSU-Iligan Institute of Technology, 9200 Iligan City, Philippines Abstract. A set S ⊆ V (G) is a hop dominating set of G if for each v ∈ V (G) \ S, there exists w ∈ S such that dG(v, w) = 2. It is a global hop dominating set of G if it is a hop dominating set of both G and the complement G of G. The minimum cardinality of a hop dominating (global hop dominating) set of G, denoted by γh(G) (resp. γgh(G)), is called the hop domination (resp. global hop domination) number of G. In this paper, we give some realization results involving domination, hop domination, and global hop domination parameters. Also, we give a rectification of a result found in a recent paper of the authors and use this to prove some results in this paper. 2020 Mathematics Subject Classifications: 05C69 Key Words and Phrases: Domination, hop domination, global hop domination, complementary prism, shadow graph 1. Introduction Domination has been a topic of interest to many researchers in the field of Graph Theory. By imposing certain additional conditions or formulating similar conditions from the standard concept, a variant can then be obtained. Indeed, the domination concept yielded several variations which have been investigated by researchers. Some of these variants can be found in [1], [2], [3], [4], [6], [7], [8], [9], [10] and [14]. Shortly after Natarajan and Ayyaswamy [13] introduced and studied the concept of hop domination in a graph, some variants of the concept emerged. The concept and some of its variants are studied in [5], [11], [12], [15], and [16]. In this paper, we show that the standard domination and hop domination parameters are generally non-comparable. It ∗Corresponding author. DOI: https://doi.org/10.29020/nybg.ejpam.v14i4.4144 Email addresses: gemma.salasalan@g.msuiit.edu.ph (G. Salasalan), sergio.canoy@g.msuiit.edu.ph (S. Canoy, Jr.) http://www.ejpam.com 1415 © 2021 EJPAM All rights reserved. G. Salasalan, S. Canoy, Jr. / Eur. J. Pure Appl. Math, 14 (4) (2021), 1415-1428 1416 is shown that the absolute difference of these parameters can be made arbitrarily large. Further, we rectify a result found in [16] and use the corrected result to prove some results in this paper. Let G = (V (G), E(G)) be a simple undirected graph. The distance between two vertices u and v of G, denoted by dG(u, v), is equal to the length of a shortest path connecting u and v. Any path connecting u and v of length dG(u, v) is called a u-v geodesic. The open neighbourhood of a vertex v of G is the set NG(v) = {u ∈ V (G) : uv ∈ E(G)} and its closed neighbourhood is the set NG[v] = NG(v) ∪ {v}. The open neighbourhood of a subset S of V (G) is the set NG(S) = ∪v∈SNG(v) and its closed neighbourhood is the set NG[S] = NG(S) ∪ S. The degree of v, denoted by degG(v), is equal to |NG(v)|. A vertex v is called a leaf in G if degG(v) = 1. The open hop neighbourhood of a vertex v of G is the set NG(v, 2) = {w ∈ V (G) : dG(v, w) = 2} and its closed hop neighbourhood is the set NG[v, 2] = NG(v, 2) ∪ {v}. The open hop neighbourhood of a subset S of V (G) is the set NG(S, 2) = ∪v∈SNG(v, 2) and its closed hop neighbourhood is the set NG[S, 2] = NG(S, 2) ∪ S. A set S ⊆ V (G) is a dominating set of G if NG[S] = V (G). A vertex v of G is a dominating vertex if {v} is a dominating set of G. The smallest cardinality of a dominating set of G, denoted by γ(G), is called the domination number of G. A dominating set of G with with cardinality γ(G) is called a γ-set of G. A set S ⊆ V (G) is a hop dominating set of G if for each x ∈ V (G) \ S, there exists z ∈ S such that dG(x, z) = 2. The smallest cardinality of a hop dominating set of G, denoted by γh(G), is called the hop domination number of G. A hop dominating set of G with cardinality γh(G) is called a γh-set of G. A set S ⊆ V (G) is a global hop dominating set of G if it is a hop dominating set of G and G. The smallest cardinality of a global hop dominating set of G, denoted by γgh(G), is called the global hop domination number of G. A global hop dominating set of G with cardinality γgh(G) is called a γgh-set of G. 2. Results We note that although hop domination is, in some sense, a variation of the standard domination concept, the associated parameters are, in general, not comparable. Our first simple result says that the absolute difference of the domination number and hop domination number can be made arbitrarily large. Proposition 1. Each of the following statements holds. (i) For each integer n ≥ 1, there exists a connected graph G such that γh(G)−γ(G) = n. (ii) For each integer n ≥ 1, there exists a connected graph G such that γ(G)−γh(G) = n. Proof. (i) LetG = Kn+1. Then γ(G) = 1 and γh(G) = n+1. Hence, γh(G)−γ(G) = n. (ii) Consider the star K1,n+2 with vertices v0, v1, v2, . . . , vn+1, vn+2, where v0 is the central vertex. Let G (see Figure 1) be the graph obtained from K1,n+2 by adding n+ 2 pendant edges v1w1, v2w2, . . . , vn+1wn+1, vn+2wn+2. Let S1 = {v1, v2, . . . , vn, vn+1, vn+2} G. Salasalan, S. Canoy, Jr. / Eur. J. Pure Appl. Math, 14 (4) (2021), 1415-1428 1417 ......... ........ ........ ........ ........ ........ ........ ........ ........ ... .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ... .................................... .................................... ............ ........... ........... ........... ........... ........... .... .................................... ............ ........... ........... ........... ........... ........... .... .................................... .................................... .......................... ......................... ......................... .... .................................... .......................... ......................... ......................... .... .................................... .................................... ....................................................................... .................................... ....................................................................... .................................... .................................... v1 w1 w2 w3 wn+2 v0 v2 v3 vn+2 ... G Figure 1 and S2 = {v0, v1}. Clearly, S1 and S2 are γ-set and γh-set of G, respectively. Thus, γ(G)− γh(G) = (n+ 2)− 2 = n. The next result is, in fact, a realization problem. Theorem 1. Let a and b be positive integers. Then each of the following statements holds. (i) If 2 ≤ a ≤ b, then there exists a connected graph G such that γh(G) = a and γ(G) = b. (ii) If 3 ≤ a ≤ b, then there exists a graph H such that γ(H) = a and γh(H) = b. Proof. (i) Suppose first that a = b. Consider the graph G in Figure 2. Clearly, S1 = {x1, x2, . . . , xa} is a γh-set and S2 = {y1, y2, . . . , ya} is a γ-set of G. Hence, γh(G) = γ(G) = a. ......... ........ ........ ........ ........ ........ ........ ........ ........ ... .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ... .................................... .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ... .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ... .................................... .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ... .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ... .................................... .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ... .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ... .................................... .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ... .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ... .................................... .................................... ................................................................................................................ ................................................................................................................ .................................... ................................................................................................................ .................................... y1 y2 y3 ya−1 ya x1 x2 x3 xa−1 xa . . . G Figure 2 Next, suppose a < b and let m = b − a. Consider the graph G in Figure 3. One can easily see that set S = {x1, x2, . . . , xa} is a γh-set of G. Hence, γh(G) = |S| = a. The set S′ = {y1, y2, . . . , ya, z1, z2, . . . , zm} is a γ-set of G and so γ(G) = |S′| = a+m = b. G. Salasalan, S. Canoy, Jr. / Eur. J. Pure Appl. Math, 14 (4) (2021), 1415-1428 1418 ......... ........ ........ ........ ........ ........ ........ ........ ........ ... .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ... .................................... .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ... .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ... .................................... .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ... .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ... .................................... .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ... .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ... .................................... .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ... .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ... .................................... .................................... ................................................................................................................ ................................................................................................................ .................................... ................................................................................................................ .................................... ............ ........... ........... ........... ........... ........... .... .................................... ............ ........... ........... ........... ........... ........... .... .................................... .................................... .......................... ......................... ......................... .... .................................... .......................... ......................... ......................... .... .................................... .................................... ....................................................................... .................................... ....................................................................... .................................... .................................... y1 y2 y3 ya−1 ya x1 x2 x3 xa−1 xa z1 z2 zm . . . ... G Figure 3 (ii) The case a = b is similar to the first case of (i). Suppose a < b and let m = b − a. Consider graph H = G ∪ Km+1, where V (Km+1) = {v1, v2, . . . , vm, vm+1} and G is the graph in Figure 4. Then S = {y1, y2, . . . , ya−1, v1} is a γ-set and S′ = {x1, x2, . . . , xa−1}∪ ......... ........ ........ ........ ........ ........ ........ ........ ........ ... .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ... .................................... .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ... .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ... .................................... .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ... .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ... .................................... .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ... .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ... .................................... .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ... .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ... .................................... .................................... ................................................................................................................ ................................................................................................................ .................................... ................................................................................................................ .................................... y1 y2 y3 ya−2 ya−1 x1 x2 x3 xa−2 xa−1 . . . G Figure 4 V (Km+1) is a γh-set ofH. Therefore, γ(H) = a and γh(H) = a−1+m+1 = a+m = b. It must be clear that every global hop dominating set is a hop dominating a set and a set is a global hop dominating set of a graph G if and only if it is a global hop dominating set of G. The following remark is immediate from these facts. Remark 1. For any graph G, γh(G) ≤ γgh(G) and γgh(G) = γgh(G). It was pointed out in [16] that 1 ≤ γgh(G) ≤ |V (G)| for any graph G and that γgh(G) = 1 if and only if G = K1. The next result is a rectification of Theorem 3.3 in [16]. Theorem 2. (Theorem 3.3 in [16]) Let G be a graph of order n ≥ 1. Then γgh(G) = n if and only if every component of G or G is complete. Moreover, if G is connected, then for each v ∈ V (G), we have (i) V (G) \NG(v) is an independent set, and (ii) NG(v) = NG(a) for each a ∈ V (G) \NG(v). Proof. Suppose γgh(G) = n. Assume first that G is disconnected and suppose that G has a component C which is not complete. Then there exist distinct vertices x, y ∈ V (C) such that dG(x, y) = dC(x, y) = 2. Let S = V (G) \ {x}. Then S is a hop dominating set of G. Let z ∈ C such that [x, z, y] is an x-y geodesic in G. Let C ′ be a component of G. Salasalan, S. Canoy, Jr. / Eur. J. Pure Appl. Math, 14 (4) (2021), 1415-1428 1419 G with C ′ ̸= C and pick any w ∈ C ′. Then [x,w, z] is an x-z geodesic in G. It follows that dG(x, z) = 2. Thus, S is a hop dominating set of G, showing that S is a global hop dominating set of G. Therefore, γgh(G) ≤ |S| = n−1, a contradiction. Accordingly, every component of G is complete. Next, suppose that G is connected. Suppose further that G is connected. Then, clearly, G ̸= Kn. Let u, v ∈ V (G) be such that dG(u, v) = 2 and let [u, p, v] be a u-v geodesic in G. Then S∗ = V (G) \ {u} is a hop dominating set of G. Since up /∈ E(G), it follows that dG(u, p) ≥ 2. It follows that there exists q ∈ S such that dG(u, q) = 2. This shows that S∗ is hop dominating set of G. Thus, S∗ is a global hop dominating set of G and γgh(G) ≤ |S∗| = n − 1, a contradiction. Therefore, G is disconnected. Since γgh(G) = γgh(G) = n, this would imply that every component of G is complete (as in the first case applied to G). For the converse, suppose first that every component of G is complete. Then, clearly, S = V (G) is the only hop dominating set of G. It follows that S is the only global hop dominating set of G. If every component of G is complete, then S is the only global hop dominating set of G. Therefore, γgh(G) = n. Now suppose G is connected and let v ∈ V (G) = V (G). Suppose there exist distinct vertices a, b ∈ V (G) \NG(v) such that ab ∈ E(G). Then [a, v, b] is an a-b geodesic in G, implying that Sa = V (G)\{a} is a hop dominating set of G. Now, since a ∈ V (G)\NG(v), it follows that dG(a, v) ≥ 2. This implies that there exists w ∈ Sa such that dG(a,w) = 2, showing that Sa is also a hop dominating set of G. Hence, γgh(G) ≤ |Sa| = n − 1, a contradiction. Therefore, V (G) \ NG(v) is an independent set, showing that (i) holds. Next, let a ∈ V (G) \NG(v). Let Cv be the component of G with v ∈ Cv. Since a ∈ NG(v) and Cv is complete, NG(a) = NG(v). This shows that (ii) holds. The next result is a consequence of Theorem 2. Corollary 1. γgh(Kn) = γgh(K1,n−1) = n for all integer n ≥ 2. Theorem 3. Let a and b be positive integers such that 2 ≤ a ≤ b. Then there exists a connected graph G such that γh(G) = a and γgh(G) = b. Proof. Consider the following cases: Case 1. a = b Let G = Ka. Then G = Ka. By Theorem 2, γh(G) = γgh(G) = a. Case 2. a < b Let k = b− a. Let V (Ka−1) = {x1, x2, . . . , xa−1} and consider the graph G in Figure 5 obtained from ⟨v⟩ + Ka−1 by adding the edges xiyj for i ∈ {1, 2, . . . , a − 1} and j ∈ {1, 2, . . . , k} (⟨v⟩ is the graph induced by {v}). G. Salasalan, S. Canoy, Jr. / Eur. J. Pure Appl. Math, 14 (4) (2021), 1415-1428 1420 ............................................................................................................................................................................................. ................................................................................................................................................................................................................................. .................................... ............... .............. .............. .............. .............. .............. .............. .............. .............. .............. .............. .......... .................................... ............... .............. .............. .............. .............. .............. .............. .............. .............. .............. .............. .......... .................................... .............................................................................................................................. .............................................................................................. .................................... .................................... ................................................................................................................................................................................................. .................................... ............................................................................................................... .................................... .......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... .................................... .................................... ........................................................................ ....................................................................... ....................................................................... .................................... .................................................. ....................................................................... ....................................................................... ....................................................................... ....................... .................................... .......................................................................................................................................................................................................................................................... .............................................................................................................................................................................................................................................................................................. .................................... .............................................................................................................................................................................................................................................................................................. .................................... .................................... ............... .............. .............. .............. .............. .............. .............. .............. .............. .............. .............. .............. .............. .............. .................................... ............... .............. .............. .............. .............. .............. .............. .............. .............. .............. .............. .............. .............. .............. .................................... .......................... ......................... ......................... ......................... ......................... ......................... .................... ...................................... ......................... ......................... ......................... ......................... ......................... ......................... ................... . ................................... ........................................................................................................................................................................... .................................... .................................... ............ ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ..... .................................... ............ ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ..... . ................................... .............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ... .................................... .............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ... .... ................................ ................................. ................................ ................................ ................................ ................................ ................................ ................................ . .................................... .................................... v x1 x2 xa−1 ... y1 y2 yk ... G Figure 5 Let S = {v} ∪ V (Ka−1) = {v, x1, x2, . . . , xa−1}. Since every vertex xi (1 ≤ i ≤ a− 1) is a dominating vertex of G, it follows that each xi is in every γh-set of G. Since dG(v, yj) = 2 for all j ∈ {1, 2, . . . , k}, it follows that S is a γh-set of G. Hence, γh(G) = a. Now, the complement G of G is the graph isomorphic to (K1 + Kk) ∪ Ka−1. By Theorem 2, γgh(G) = |V (G)| = (k + 1) + (a− 1) = b. Corollary 2. For each positive integer n, there exists a connected graph G such that γgh(G)− γh(G) = n. In other words, the difference γgh− γh can be made arbitrarily large. Proof. Let n be a positive integer. By Theorem 3, there exists a connected graph G such that γh(G) = n+ 1 and γgh(G) = 2n+ 1. Hence, γgh(G)− γh(G) = n. For a graph G, the complementary prism, denoted by 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. In simple terms, the graph GG is formed from G ∪G by adding the edge vv for every vertex v ∈ V (G). The next result gives bounds for the domination number of the complementary prism of a graph. Theorem 4. [10] For any graph G, max{γ(G), γ(G)} ≤ γ(GG) ≤ γ(G) + γ(G). Theorem 5. Let G be a connected graph of order n. Then each of following holds. (i) If G is a non-trivial graph such that γ(G) = 1, then γ(GG) = 1 + γ(G \ v), where v is a dominating vertex of G. In particular, γ(KnKn) = n. (ii) If n ≥ 1, then γh(GG) = 2. In particular, {v, v} is γh-set of GG for each v ∈ V (G). (iii) If n ≥ 2, then γgh(GG) ≤ min{n, 2γgh(G)}. Proof. (i) Let v be a dominating vertex of G and let D be a dominating set of G \ v. Since (V (G)\{v})∪{v} ⊆ NGG(v) and V (G)\{v} ⊆ NGG(D), S = D∪{v} is a dominating set of GG. This implies that γ(GG) ≤ 1 + |D| = 1 + γ(G \ v). G. Salasalan, S. Canoy, Jr. / Eur. J. Pure Appl. Math, 14 (4) (2021), 1415-1428 1421 Suppose now that S0 is a γ-set of GG. Since v is a dominating vertex of G, v is an isolated vertex of G (and so a leaf in GG). Hence, v ∈ S0 or v ∈ S0. Suppose v /∈ S0. Then v ∈ S0. Suppose S1 = S0∩V (G) = ∅. Since NGG(w)∩V (G) = {w} for each w ∈ V (G), it follows that S0 = V (G). Hence, γ(GG) = |S0| = n ≥ 1+γ(G\v). Suppose S1 ̸= ∅ and let S2 = S0 ∩ (V (G) \ {v}). If S2 is a dominating of G \ v, then γ(GG) = |S0| ≥ 1+ γ(G \ v). Suppose R = V (G \ v) \ NG\v[S2] ̸= ∅ and set RG = {w ∈ V (G) \ {v} : w ∈ R}. Then necessarily, RG ⊆ S1. Thus, γ(GG) = |S0| = 1+ |S1|+ |S2| ≥ 1+ |RG|+ |S2| ≥ 1+γ(G\v). Next, suppose that v ∈ S0. Since S0 is a γ-set of GG and v is a leaf of GG, v /∈ S. Let D1 = (V (G) \ {v}) ∩ S0. If D1 = ∅, then D2 = (V (G) ∩ S0 must be a dominating set of G \ v. It follows that γ(GG) = |S0| ≥ 1 + γ(G \ v). Suppose that D1 ̸= ∅. If D2 = ∅, then D1 = V (G) \ {v}. It follows that S0 = V (G) and γ(GG) = |S0| = n ≥ 1 + γ(G \ v). Suppose D2 ̸= ∅ and let D∗ 2 = V (G \ v) \ NG\v[D2].Since S0 is a γ-set and v ∈ S0, it follows that D∗ 2 = {x : x ∈ D1} and |D∗ 2| = |D1|. Clearly, D′ = D2 ∪D∗ 2 is a dominating set of G \ v and so γ(GG) = |S0| = 1+ |D1|+ |D2| = 1+ |D′| ≥ 1 + γ(G \ v). This proves the desired equality. Thus, in particular, if G = Kn, then γ(KnKn) = n. (ii) If n = 1, then GG = K2. Hence, γh(GG) = 2. Suppose n ≥ 2. Let v ∈ V (G) and let S = {v, v}. Let w ∈ V (G) \ {v}. If wv ∈ E(G), then [w, v, v] is a w-v geodesic in GG. If wv /∈ E(G), then w v ∈ E(G). It follows that [w,w, v] is a w-v geodesic in GG. Next, let z ∈ V (G) \ {v}. If z v ∈ E(G), then [z, v, v] is a z-v geodesic in GG. If z v /∈ E(G), then zv ∈ E(G) and [z, z, v] is a z-v geodesic in GG. Thus, S is a hop dominating set of G. Since GG is non-trivial, it follows that γh(GG) = 2. (iii) Suppose n ≥ 2. Let S = V (G) and let v ∈ V (GG) \ S = V (G). Since G is connected and non-trivial, we may choose any w ∈ V (G) ∩ NG(v). Consequently, [v, v, w] is a v-w geodesic in GG. Hence, dGG(v, w) = 2. Since v was arbitrarily chosen, it follows that S = V (G) is a hop dominating set of GG. Next, let y ∈ V (GG) \ S. Then yy /∈ E(GG). Pick any x ∈ V (G) \ {y}. If xy ∈ E(GG), then x y ∈ E(GG). Since yx ∈ E(GG), it follows that d GG (y, y) = 2. If xy /∈ E(GG), then xy ∈ E(GG). Since xy ∈ E(GG), d GG (y, y) = 2. This shows that S is also a hop dominating set of GG. Therefore, S is a global hop dominating set of GG and γgh(GG) ≤ |S| = n. Now let SG be a global hop dominating set of G and let SG = {v : v ∈ SG}. Then clearly, S′ = SG ∪ SG is a hop dominating set of both GG and GG, that is, S′ is a global hop dominating set of GG. Thus, in particular, if SG is a γgh-set of G, then S′ = SG ∪SG is a global hop dominating set of GG. This implies that γgh(GG) ≤ |S′| = 2γgh(G). Combining this with the first inequality, we find that the assertion in (iii) holds. The bound given in Theorem 5(iii) is sharp. To see this, consider the graph G = P3 and the graph H obtained from C4 by adding a pendant edge. It can be verified that γgh(GG) = |V (G)| = 3 and γgh(HH) = 2γgh(H) = 4 < 5 = |V (H)|. Theorem 6. Let G = Km1,m2,...,mk be a complete multipartite graph such that m1 ≤ m2 ≤ G. Salasalan, S. Canoy, Jr. / Eur. J. Pure Appl. Math, 14 (4) (2021), 1415-1428 1422 . . . ≤ mk and k ≥ 2. Then γ(GG) =  k if m1 = 1 k + 1 if m1 = 2 k + 2 if m1 ≥ 3. Proof. Let U1, U2, . . . , Uk be the partite sets of G with |Ui| = mi for each i ∈ {1, 2, . . . , k}. For each i ∈ {1, 2, . . . , k}, let U i = {v : v ∈ Ui}. Then the induced graphs of the sets U1, U2, . . . , Uk are exactly the (complete) components of G in GG. Suppose first that m1 = 1, say U1 = {v}. Then v is a dominating vertex of G and so by Theorem 5(i), γ(GG) = 1+ γ(G \ v). Since G \ v is the disjoint union of complete graphs ⟨U2⟩, ⟨U3⟩, . . . , ⟨Uk⟩, it follows that γ(G \ v) = k − 1. Thus, γ(GG) = k. Next, suppose that m1 = 2, say U1 = {u, v}. By Theorem 4, max{γ(G), γ(G)} = k ≤ γ(GG) ≤ k + 2 = γ(G) + γ(G). For each i ∈ {2 . . . , k}, choose any vi ∈ Ui and let S = {u, v} ∪ {vi : i ∈ {2, 3, . . . , k}}. Then S is a dominating set of GG. Hence, γ(GG) ≤ |S| = 2 + k − 1 = k + 1. Let S′ be a γ-set of GG. If S′ ∩ V (G) = ∅ or S′ ∩ V (G) = ∅, then |S′| = |V (G)| = ∑k i=1mi ≥ 2k > k + 1 which is not possible. Thus, S′ ∩ V (G) ̸= ∅ and S′ ∩ V (G) ̸= ∅. Clearly, S′ ∩ (Ui ∪ U i) ̸= ∅ for all i ∈ {1, 2, . . . , k}. Suppose S′ ∩ U1 ̸= ∅. If |S′ ∩ U1| = 1, say v ∈ S′ ∩ U1, then V (G) \ {u, v} ⊆ NGG(v). Since S′ is a γ-set of GG and u /∈ S′, |S′ ∩ U1| = 1. We may assume that u ∈ S′. Let j ∈ {2, 3, . . . , k} and suppose that S ∩ U j = ∅. Then necessarily, Uj ⊆ S′. Pick any w ∈ U j and let Sw = (S′ \Uj)∪ {w}. Then Sw is a dominating set of GG. Since |Uj | ≥ 2, γ(GG) = |S′| > |Sw|, a contradiction. Therefore, S′ ∩ U j ̸= ∅ for each j ∈ {2, 3, . . . , k}. Moreover, because S′ is a γ-set of GG, |S′ ∩ U j | = 1 for all j ∈ {2, 3, . . . , k}. Thus, γ(GG) = |S′| ≥ k + 1. If |S′ ∩ U1| = 2, then S′ ∩ U1 = ∅. Since S′ ∩ (Ui ∪ U i) ̸= ∅ for all i ∈ {2, . . . , k}, it follows that γ(GG) = |S′| ≥ k + 1. Suppose now that S′ ∩ U1 = ∅. If |S′ ∩ U1| = 1, then there exists j ̸= 1 such that S′ ∩ Uj ̸= ∅. If |S′ ∩ Uj | = 1, then |S′ ∩ U j | ≠ 0. Since S′ ∩ (Ui ∪ U i) ̸= ∅ for all i ∈ {2, . . . , j − 1, j + 2, . . . , k}, it follows that γ(GG) = |S′| ≥ k + 1. If |S′ ∩ Uj | ≥ 2, then clearly, γ(GG) = |S′| ≥ k + 1. Therefore,γ(GG) = k + 1. Finally, let m1 ≥ 3. Let S be a γ-set of GG. Since γ(GG) ≤ k+2 (by Theorem 4) and |V (G)| = ∑k i=1mi > k + 2, S ∩ V (G) ̸= ∅ and S ∩ V (G) ̸= ∅. Again, S ∩ (Ui ∪ U i) ̸= ∅ for each i ∈ {1, 2, . . . , k}. Suppose S ∩ U1 = ∅. Then S ∩ U1 ̸= ∅. If |S ∩ U1| ≥ 3, then γ(GG) = |S| ≥ k + 2. So suppose that |S ∩ U1| ≤ 2. Then there exists j ̸= 1 such that S ∩Uj ̸= ∅. If S ∩Uj = Uj , then γ(GG) = |S| ≥ k + 2. If S ∩Uj ̸= Uj , then S ∩U j ̸= ∅. Hence, if |S∩U1| = 2, then γ(GG) = |S| ≥ k+2. Suppose now that |S∩U1| = 1. Suppose further that |S ∩ (Uj ∪ U j)| = 2. Then there exists r ̸= 1, j such that |S ∩ (Ur ∪ U r)| ≥ 2. Thus, γ(GG) = |S| ≥ k + 2. Next, suppose that S ∩ U1 ̸= ∅. Suppose S ∩ Uj = ∅ for all j ≥ 2. Since S is a γ-set of GG and Uj ⊆ NGG(S ∩ U1) for all j ≥ 2, |S ∩ U j | = 1 for all j ≥ 2 and |S| = k−1+ |U1|. If m1 = |U1| = 3, then |S| = k−1+3 = k+2. However, if m1 ≥ 4, then |S| = k− 1+ |U1| ≥ k+3, contrary to the fact that k+2 is an upper bound of |S|. Hence, for m1 ≥ 4, there exists j ≥ 2 such that |S ∩ (Uj ∪ U j)| ≥ 2. Since |S ∩ (U1 ∪ U1)| ≥ 2, S G. Salasalan, S. Canoy, Jr. / Eur. J. Pure Appl. Math, 14 (4) (2021), 1415-1428 1423 is a γ-set, γ(GG) = |S| ≥ k+2. Note that we obtain the same implications if m1 = 3 and S ∩ Uj ̸= ∅ for some j ≥ 2. Accordingly, γ(GG) = k + 2. Given a graph G with γ(G) = 1, we denote by Dom(G) the set {v ∈ V (G) : {v} is a dominating set of G}. Lemma 1. Let G be a graph with γ(G) = 1 and let S be a global hop dominating set of GG. If v ∈ Dom(G), then v ∈ S or v ∈ S. Proof. Let v ∈ Dom(G) and suppose that v, v /∈ S. Since S is a global hop dominating set of GG, it is a hop dominating set of GG. As v ∈ V (GG) \ S, there exists z ∈ S such that d GG (v, z) = 2. However, d GG (v, x) = 1 for all x ∈ V (GG) \ {v, v}. Since v /∈ S, it follows that such a vertex z does not exist, contrary to the assumption that S is a hop dominating set of of GG. Therefore, v ∈ S or v ∈ S. Corollary 3. For each positive integer n ≥ 2, γgh(KnKn) = n. Proof. By Theorem 5(iii), γgh(KnKn) ≤ n. Let S be a γgh-set of KnKn. Since Dom(Kn) = V (Kn), γgh(KnKn) = |S| ≥ n by Lemma 1. Therefore, γgh(KnKn) = n. Theorem 7. Let G = Km1,m2,...,mk be a complete multipartite graph such that 1 ≤ m1 ≤ m2 ≤ . . . ≤ mk, where k ≥ 2 and mj ≥ 2 for some j with 1 ≤ j ≤ k. Then γgh(GG) = { k if m1 = m2 = 1 and k ≥ 4 k + 1 otherwise. Proof. Let U1, U2, . . . , Uk be the partite sets of G with |Ui| = mi for each i ∈ {1, 2, . . . , k}. Again, for each i ∈ {1, 2, . . . , k}, let U i = {v : v ∈ Ui}. Choose any vi ∈ Ui for each i ∈ {1, 2, . . . , k}. Suppose m1 = m2 = 1 and k ≥ 4. Then U1 = {v1} and U2 = {v2}. Let S = {v1, v2, v3, v4, . . . , vk}. Then dGG(v1, v2) = 2 and dGG(v2, v1) = 2. For each j ∈ {3, 4, . . . , k}, we have dGG(w, v1) = 2 for each w ∈ Uj \ S and dGG(x, vr) = 2 for each x ∈ Uj , where r ≥ 3 and r ̸= j. Thus, S is a hop dominating set of GG. On the other hand, d GG (v1, v1) = 2 and d GG (v2, v2) = 2. For each j ∈ {3, 4, . . . , k}, we have d GG (w, vj) = 2 for each each w ∈ Uj \ S and d GG (x, v1) = 2 for each each x ∈ Uj . Thus, S is a hop dominating set of GG. Therefore, S is a global hop dominating set of GG and γgh(GG) ≤ |S| = k. Next, let S0 be a γgh-set of GG. Suppose there exists j ∈ {1, 2, . . . , k} such that S0∩(Uj∪U j) = ∅. Let w ∈ U j . It follows from the adjacency in GG that d GG (w, p) = 1 for all p ∈ V (GG)\(U j∪{w}). Hence, by assumption, there exists no q ∈ S0 with d GG (w, q) = 2, contrary to the fact that S0 is a hop dominating set of GG. Therefore, S0∩(Uj∪U j) ̸= ∅ for each j ∈ {1, 2, . . . , k}. Consequently, γgh(GG) = |S| ≥ k. Accordingly, γgh(GG) = k. G. Salasalan, S. Canoy, Jr. / Eur. J. Pure Appl. Math, 14 (4) (2021), 1415-1428 1424 Suppose now that the conditions m1 = m2 = 1 and k ≥ 4 do not hold. Let S′ = {v1, v1, v2, v3, . . . , vk}. By Theorem 5(ii), {v1, v1} is a hop dominating set of GG. Hence, S is a hop dominating set of GG. Let v′ ∈ Uj \ {v1}, where j ∈ {1, 2, . . . , k}. Then [v′, v1, v2] is a v′-v2 geodesic in GG. Hence, d GG (v′, v2) = 2. Let j ∈ {1, 2, . . . , k} and pick any i ∈ {1, 2, . . . , k} \ {j}. Then for y ∈ U j \{vj}, we find that [y, vi, vj ] is a y-vj geodesic in GG. Hence, d GG (y, vj) = 2. This shows that S′ is a hop dominating set of GG. Therefore, S′ is a global hop dominating set of GG and γgh(GG) ≤ |S′| = k + 1. Let S0 be a γgh-set of GG. As shown and seen earlier S0 ∩ (Uj ∪ U j) ̸= ∅ for each j ∈ {1, 2, . . . , k}. Next, suppose there exists j ∈ {1, 2, . . . , k} with mj ≥ 2 such that |S0 ∩ U j | = 0. Let a ∈ U j . Since d GG (a, p) = 1 for p ∈ V (GG) \ (U j ∪ {a}) and |S0 ∩ U j | = 0, it follows that a ∈ S0. Thus, Uj ⊆ S0. Since mj ≥ 2, it follows that γgh(GG) = |S0| ≥ k + 1. Suppose that |S0 ∩ U j | ̸= 0 for each j with mj ≥ 2. If |S0 ∩ U j | ≥ 2 for some j with mj ≥ 2, then γgh(GG) = |S0| ≥ k + 1. Suppose that |S0 ∩ U j | = 1 for each j with mj ≥ 2. For a j satisfying this property, pick y ∈ U j \ S0. Since S is a hop dominating set of GG and the induced graph of U j is a complete graph in GG, it follows that there exists r ̸= j such z ∈ Ur ∩S0 and dGG(y, z) = 2. If an r exists such that mr ≥ 2, then this would imply that γgh(GG) = |S0| ≥ k + 1. So suppose that there exists no such r with mr ≥ 2. Then mr = 1 and r = 1 or r = 2, say Ur = U1. If z ∈ S0, then γgh(GG) = |S0| ≥ k + 1. Suppose z /∈ S0. Then there exists p ∈ Us ∩ S0 for some s ≥ 2 such that dGG(z, p) = 2. If ms = 1, then s = 2 and j = k = 3 by assumption. If p ∈ S0, then γgh(GG) = |S0| ≥ k + 1. Suppose p /∈ S0 and let S0 ∩ U j = {q}. Since S0 is a hop dominating set of GG, z, p /∈ S0, and k = 3, we must have q ∈ S0. Hence, γgh(GG) = |S0| ≥ k + 1. Now, if ms ≥ 2, then s = k by assumption. This implies that |S0∩(Uj∪U j)| ≥ 2, showing that γgh(GG) = |S0| ≥ k+1. Therefore, γgh(GG) = k+1. The shadow graph D2(G) of a graph G is the graph obtained by taking two copies of G, say G1 and G2, and joining each vertex u ∈ V (G1) to the neighbors of the corresponding vertex u′ ∈ V (G2). Lemma 2. Let G be a non-trivial connected graph and let G1 and G2 be copies of G in the graph D2(G). If w ∈ V (G1) and w′ ∈ V (G2) is the corresponding vertex of w, then ND2(G)[w, 2] = NG1 [w, 2] ∪NG2 [w ′, 2] = ND2(G)[w ′, 2]. Proof. Clearly, NG1 [w, 2] ∪NG2 [w ′, 2] ⊆ ND2(G)[w, 2]. Now let x ∈ ND2(G)[w, 2]. Then x = w or dD2(G)(w, x) = 2. Suppose first that x ∈ V (G1). If x = w, then x ∈ NG1 [w, 2]. Suppose that dD2(G)(w, x) = 2 and let y ∈ V (D2(G)) such that [w, y, x] is w-x geodesic in D2(G). If y ∈ V (G1), then [w, y, x] is a w-x geodesic inG1. Suppose y ∈ V (G2), say y = u′. By definition of D2(G), it follows that u ∈ V (G1) and [w, u, x] is a w-x geodesic in G1. Hence, x ∈ NG1 [w, 2]. Next, suppose that x = z′ ∈ V (G2). If y ∈ V (G1), then [w′, y′, z′] is a w-x geodesic in G2. Suppose y ∈ V (G2), say y = u′. Then [w′, u′, z′] is w′-x geodesic in G2. Hence, x ∈ NG2 [w ′, 2]. Thus, ND2(G)[w, 2] ⊆ NG1 [w, 2] ∪NG2 [w ′, 2], showing that G. Salasalan, S. Canoy, Jr. / Eur. J. Pure Appl. Math, 14 (4) (2021), 1415-1428 1425 ND2(G)[w, 2] ⊆ NG1 [w, 2] ∪ NG2 [w ′, 2]. Similarly, ND2(G)[w ′, 2] ⊆ NG1 [w, 2] ∪ NG2 [w ′, 2]. Therefore, ND2(G)[w, 2] = NG1 [w, 2] ∪NG2 [w ′, 2] = ND2(G)[w ′, 2]. A result in [13] says that γh(D2(G)) = γh(G) for any graph G. This, however, is not true if G contains an isolated vertex. Indeed, if G is the trivial graph and H is the (disjoint) union K1 ∪ K1 ∪ P2, then D2(G) = K2 and D2(G) = K2 ∪ K2 ∪ C4. Hence, γh(D2(G)) = 2 ̸= 1 = γh(G) and γh(D2(H)) = 6 ̸= 4 = γh(G). Theorem 8. Let G be a non-trivial graph. Then the following hold. (i) If G is connected, then γh(D2(G)) = γh(G). (ii) If G is disconnected with r trivial components and k non-trivial components G1,G2, G3, . . . , Gk, then γh(D2(G)) = 2r + ∑k i=1 γh(Gk). Proof. (i) Let G1 and G2 be the two copies of G in the definition of D2(G). Let S be a γh-set of G1 and let v′ ∈ V (G2). If the corresponding vertex v ∈ V (G1) is in S, then dD2(G)(v, v ′) = 2. So suppose v /∈ S. Since S is a hop dominating set of G1, there exists w ∈ S such that dG1(v, w) = 2. Let [v, z, w] be a v-w geodesic in G1. Then v′z, zw ∈ E(D2(G)). Since v /∈ NG1(w), v′w /∈ E(D2(G)). Thus, dD2(G)(w, v ′) = 2. Therefore, S is a hop dominating set of D2(G) and γh(D2(G) ≤ |S| = γh(G). Next, suppose that S′ is a γh-set of D2(G). Let S1 = S′∩V (G1) and S2 = S′∩V (G2). If S1 = S′ or S2 = S′, then S′ is a hop dominating set of G1 or G2. Hence, γh(D2(G) = |S′| ≥ γh(G). Suppose S1 ̸= ∅ and S2 ̸= ∅. If S1 is a hop dominating set of G1 or S2 is a hop dominating set of G2, then, as seen earlier, S1 or S2 is a hop dominating set of D2(G), contrary to the assumption that S′ is a γh-set of D2(G). Hence, none of these two sets is a hop dominating set. Let DG = {v ∈ V (G1) \ S1 : v /∈ NG1(S1, 2)} = V (G1) \NG1 [S1, 2] and let SG = {v ∈ V (G1) \ S1 : v′ ∈ S2}. Clearly, if v ∈ SG, then v′ ∈ S2. Now let y′ ∈ S2. Then ND2(G)[y ′, 2] = ND2(G)[y, 2] by Lemma 2. Since S′ is a γh-set of D2(G), it follows that y ∈ V (G1) \ S1, that is, y ∈ SG. Hence, |SG| = |S2|. Since S′ is a hop dominating set of D2(G), DG ⊆ ND2(G)[S2, 2]. This means that if w ∈ DG, then there exists z′ ∈ S2 such that w ∈ ND2(G)[z ′, 2]. Consequently, z ∈ SG and by Lemma 2, we have w ∈ ND2(G)[z, 2] = NG1 [z, 2]. Thus, DG ⊆ NG1 [SG, 2], showing that S1 ∪ SG is a hop dominating set of G1. Therefore, γh(G) = γh(G1) ≤ |S1 ∪ SG| = γh(D2(G)). This establishes the desired equality. (ii) This follows from (i) and the fact that the hop domination of a (disconnected) graph is the sum of the hop domination numbers of its components. Theorem 9. Let G be a non-trivial connected graph. Then γgh(D2(G)) ≤ 2γgh(G). Proof. Let G1 and G2 be the two copies of G in the definition of D2(G). Let S1 be a γgh-set of G1 and let S2 = {v′ ∈ V (G2) : v ∈ S1}. Then S2 is a γgh-set of G2. Hence, S = S1 ∪ S2 is a hop dominating set of D2(G). Since S1 and S2 are also γgh-sets of G1 and G2, respectively, it follows that S = S1∪S2 is a hop dominating set of D2(G). Hence, S = S1 ∪ S2 is a global hop dominating set of D2(G) and γgh(D2(G)) ≤ |S| = 2γgh(G). The next result is easy. G. Salasalan, S. Canoy, Jr. / Eur. J. Pure Appl. Math, 14 (4) (2021), 1415-1428 1426 Lemma 3. Let G be a non-trivial graph. Then each of the following statements is true. (i) D2(G) is not a complete graph. (ii) D2(G) is connected if and only if G is connected. Lemma 4. Let G be a graph of order n. Then each of the following statements is true. (i) Every component of D2(G) is a complete graph if and only if G = Kn. (ii) Every component of D2(G) is a complete graph if and only if G = Kn or G = Km1,m2,...,mk , where k∑ i=1 mi = n. Proof. Let G1 and G2 be the two copies of G in the definition of D2(G). (i) Suppose every component of D2(G) is a complete graph. Suppose further that G has a non-trivial component H. Then D2(H) is a component of D2(G) which is not complete by Lemma 3, a contradiction to our assumption of D2(G). Therefore, every component of G is trivial, i.e., G = Kn. The converse is clear. (ii) Suppose that every component of D2(G) is a complete graph. If D2(G) is connected, then D2(G) = K2n. Hence, G = Kn. Next, suppose that D2(G) is disconnected with components C1, C2, . . . , Ck. For each i ∈ {1, 2, . . . , k}, let S1,i = V (G1) ∩ V (Ci), S2,i = V (G2) ∩ V (Ci) and mi = |S1,i|. Note that v ∈ S1,i if and only if v′ ∈ S2,i and that Ci = ⟨S1,i∪S2,i⟩ for each i ∈ {1, 2, . . . , k}. Let i, j ∈ {1, 2, . . . , k} with i ̸= j. Since Ci and Cj are complete subgraphs (components) of D2(G), it follows that in graph D2(G), S1,i and S1,j are independent subsets of V (G1) and xy ∈ E(G1) for each x ∈ S1,i and y ∈ S1,j . It follows that G1 is a complete multipartite graph with partite sets S1,1, S1,2, . . . , S1,k. Hence, G = Km1,m2,...,mk . The converse is clear. Theorem 10. Let G be a graph of order n. Then γgh(D2(G)) = 2n if and only if G = Kn or G = Km1,m2,...,mk , where k∑ i=1 mi = n. Proof. By Theorem 2, γgh(D2(G)) = 2n if and only if every component of D2(G) or D2(G) is complete. Thus by Lemma 4, γgh(D2(G)) = 2n if and only if G = Kn or G = Km1,m2,...,mk , where k∑ i=1 mi = n. Note that Theorem 10 shows that the bound given in Theorem 9 is tight. Conclusion: The domination and hop domination parameters are, in general, not com- parable. However, a result shows that the absolute difference of the domination number and hop domination number can be made arbitrarily large. On the other hand, a result shows a relationship of the hop domination and global hop domination numbers. REFERENCES 1427 For any non-trivial connected graph G, it is proved that that 2γgh(G) is a tight bound for the global hop domination number of the shadow graph D2(G) of G. The authors are still unable to show that the strict inequality in Theorem 9 is also attainable. We leave to the interested readers to verify whether or not equality in this result holds. Acknowledgements The authors would like to thank the referees for reading the initial manuscript and the invaluable comments and suggestion they have given. Also, the authors are grateful to the Department of Science and Technology - Accelerated Science and Technology and Hu- man Resource Development Program (DOST-ASTHRDP), Philippines, and MSU-Iligan Institute of Technology for funding this research. References [1] B. Arriola and S. Jr. Canoy. Secure doubly connected domination in graphs. Inter- national Journal of Mathematical Analysis, 8:1571–1580, 2014. [2] A. Cabaro, S. Jr. Canoy, and I. Aniversario. Secure connected domination in a graph. International Journal of Mathematical Analysis, 8(42):2065–2074, 2014. [3] S. Jr. Canoy, S.A. Canoy, and M. Cruzate. Global domination in a graph. Advances and Applications in Discrete Mathematics, 19(4):401–408, 2018. [4] S. Jr. Canoy and G. Malacas. Determining the intruder’s location in a given network: Locating-dominating sets in a graph. NRCP Research Journal., 13(1):1–8, 2013. [5] S. Jr. Canoy, R. Mollejon, and J.G. Canoy. Hop dominating sets in graphs under binary operations. European Journal of Pure and Applied Mathematics, 12(4):1455– 1463, 2019. [6] H. Escuardo, R. Gera, A. Hansberg, A.J. Rad, and L. Volkman. Geodetic domination in graphs. Journal of Combinatorial Mathematics and Combinatorial Computing, 77:89–101, 2011. [7] T. Haynes, S. Hedetniemi, and P. Slater. Domination in Graphs, Advanced Topics. Marcell Dekker, New York, USA, 1998. [8] T. Haynes, S. Hedetniemi, and P. Slater. Fundamentals of Domination in Graphs. Marcell Dekker, New York, USA, 1998. [9] T. Haynes, M. Henning, and J. Howard. Locating and total dominating sets in trees. Discrete Applied Mathematics, 154(8):1293–1300, 2006. [10] T. Haynes, M. Henning, and L. van der Merwe. Domination and total domination in complementary prisms. Journal of Combinatorial Optimization, 18:23–37, 2009. REFERENCES 1428 [11] M. Henning and N.J. Rad. On 2-step and hop dominating sets in graphs. Graphs and Combinatorics, 33(4):913–927, 2017. [12] G. Mahadevan and V. Vijayalakshmi. Clone hop domination number of a graph. Journal of Discrete Mathematical Sciences and Cryptography, 22(5):719–729, 2019. [13] C. Natarajan and S. Ayyaswamy. Hop domination in graphs II. Versita, 23(2):187– 199, 2015. [14] B. Omamalin, S. Jr. Canoy, and H. Rara. Locating total dominating sets in the join, corona, and composition of graphs. Applied Mathematical Sciences, 8(48):2363–2374, 2014. [15] Y. Pabilona and H. Rara. Connected hop domination in graphs under some binary operations. Asian-European Journal of Mathematics, 11(5):1850075–1–1850075–11, 2018. [16] G. Salasalan and S. Jr. Canoy. Global hop domination numbers of graphs. European Journal of Pure and Applied Mathematics, 14(1):112–125, 2021.