EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS Vol. 14, No. 1, 2021, 112-125 ISSN 1307-5543 – ejpam.com Published by New York Business Global Global Hop Domination Numbers of Graphs Gemma P. Salasalan 1,∗, Sergio R. Canoy, Jr.1 1 Department of Mathematics and Statistics, College of Science and Mathematics, Center for 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 global hop dominating set of G, denoted by γgh(G), is called the global hop domination number of G. In this paper, we study the concept of global hop domination in graphs resulting from some binary operations. 2020 Mathematics Subject Classifications: 05C69 Key Words and Phrases: Hop domination, global hop domination, join, corona, lexicographic product, and Cartesian product 1. Introduction Domination is a well-studied topic in Graph Theory. From the standard concept, many other variations of domination have been investigated by researchers. Connected, total, independent, and global domination are among the numerous well-known variants of the standard domination concept. Other variants may be found in the two books authored by Haynes et al. (see [5] and [6]). Recently, Natarajan and Ayyaswamy [10] introduced and studied the concept of hop domination in a graph. In another study, Ayyaswamy et al. [1] investigated the same concept and gave bounds of the hop domination number of some graphs. Henning and Rad [7] also studied the concept and answered a question posed by Ayyaswamy and Natarajan in [10]. They showed that the hop dominating set problem is NP-complete for planar bipartite graphs and planar chordal graphs. Hop domination and some of its variants are studied in [3], [8], [9], and [11]. In this paper, we study another variation of hop domination called global hop domination. This is obviously the analogue to global domination studied in [2] and [4]. ∗Corresponding author. DOI: https://doi.org/10.29020/nybg.ejpam.v14i1.3916 Email addresses: gemma.salasalan@g.msuiit.edu.ph (G. Salasalan), sergio.canoy@g.msuiit.edu.ph (S. Canoy, Jr.) http://www.ejpam.com 112 c© 2021 EJPAM All rights reserved. G. Salasalan, S. Canoy, Jr. / Eur. J. Pure Appl. Math, 14 (1) (2021), 112-125 113 Let G = (V (G), E(G)) be a simple 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)|. The minimum degree of G is δ(G) = min{degG(v) : v ∈ V (G)} and its maximum degree is ∆(G) = max{degG(v) : v ∈ V (G)}. The open hop neighbourhood of vertex v of G is the setNG(v, 2) = {w ∈ V (G) : dG(v, w) = 2}. A set S ⊆ V (G) is a dominating set (resp. total dominating set) of G if NG[S] = V (G) (resp. NG(S) = V (G)). The smallest cardinality of a dominating (resp. total dominating) set of G, denoted by γ(G) (resp. γt(G)), is called the domination number (resp. total domination number) of G. A dominating (resp. total dominating) set of G with cardinality γ(G) (resp. γt(G)), is called a γ-set (resp. γt-set) of G. It should be noted that only graphs without isolated vertices admit total dominating sets. 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. A set D ⊆ V (G) is a pointwise non-dominating set of G if for each v ∈ V (G)\D, there exists u ∈ D such that v /∈ NG(u). The smallest cardinality of a pointwise non-dominating set of G, denoted by pnd(G), is called the pointwise non-domination number of G. A dominating set S which is also a pointwise non-dominating set of G is called a dominating pointwise non-dominating set of G. The smallest cardinality of a dominating pointwise non-dominating set of G will be denoted by γpnd(G). Any pointwise non-dominating (resp. dominating pointwise non-dominating) set of G with cardinality pnd(G) (resp. γpnd(G)), is called a pnd-set (resp. γpnd-set) of G. These concepts and parameters have been defined and used in [3] and [9]. 2. Results It is worth mentioning here that every graph G admits a global hop dominating set. Indeed, the vertex set V (G) of G is a global hop dominating set. Further, we have Remark 1. 1 ≤ γgh(G) ≤ |V (G)| for any graph G. Moreover, γgh(G) = 1 if and only if G = K1. Theorem 1. Let G be a non-trivial graph. Then γgh(G) = 2 if and only if there exist distinct vertices x and y of G satisfying the following conditions: G. Salasalan, S. Canoy, Jr. / Eur. J. Pure Appl. Math, 14 (1) (2021), 112-125 114 (i) NG(x, 2) ∩NG(y, 2) = ∅ and V (G) \ {x, y} = NG(x, 2) ∪NG(y, 2); (ii) NG(x, 2) = NG(y) \ {x} and NG(y, 2) = NG(x) \ {y}; and (iii) if xy ∈ E(G), then NG(x)\NG(w) 6= ∅ for each w ∈ NG(x, 2) and NG(y)\NG(v) 6= ∅ for each v ∈ NG(y, 2). Proof. Suppose γgh(G) = 2. Let S = {x, y} be γgh-set of G. Suppose there exists z ∈ NG(x, 2)∩NG(y, 2). Then xz, yz ∈ E(G). This implies that dG(x, z) 6= 2 and dG(y, z) 6= 2. Hence, S is not hop dominating set of G, a contradiction. Thus, NG(x, 2)∩NG(y, 2) = ∅. Further, V (G)\{x, y} = NG(x, 2)∪NG(y, 2) because S is a hop dominating of set G. This shows that (i) holds. Now let z ∈ NG(x, 2). Then z /∈ S and xz ∈ V (G). Since S is hop dominating set of G, it follows that z ∈ NG(y, 2). This implies that z ∈ NG(y) \ {x}. On the other hand, if u ∈ NG(y) \ {x}, then u ∈ NG(x, 2) since S is a hop dominating of set G. Therefore, NG(x, 2) = NG(y) \ {x}. Similarly, NG(y, 2) = NG(x) \ {y}, showing that (ii) holds. Next, suppose that xy ∈ E(G) and let w ∈ NG(x, 2). Then w /∈ S and xw ∈ E(G). Since S is a hop dominating set of G, w ∈ NG(y, 2). Hence, there exists z ∈ V (G)\S such that z ∈ NG(w) ∩ NG(y). It follows that z ∈ NG(x) \ NG(w), i.e., NG(x) \ NG(w) 6= ∅. Similarly, NG(y) \NG(v) 6= ∅ for each v ∈ NG(y, 2), showing that (iii) holds. Conversely, suppose that there exist distinct vertices x and y of G satisfying conditions (i), (ii), and (iii). Let S = {x, y}. By (i), S is a hop dominating set of G. Let v ∈ V (G)\S. Assume, without loss of generality, that v ∈ NG(x, 2). Then v ∈ NG(y) \ {x} by (ii). Suppose xy /∈ E(G). Then xy, xv ∈ E(G). Thus, dG(y, v) = 2. Next, suppose that xy ∈ E(G). Then by (iii), there exists z ∈ NG(x) \ NG(v). Hence, z ∈ NG(v) ∩ NG(y), i.e., dG(y, v) = 2. Therefore, S is a global hop dominating set of G. Accordingly, γgh(G) = 2. Theorem 2. Let G be a graph of order n ≥ 2. Then γgh(G) = n if and only if one of the following statements holds: (i) Every component of G is complete. (ii) For each v ∈ V (G), V (G) \ NG(v) is an independent set and NG(v) = NG(a) for each a ∈ V (G) \NG(v). Proof. Suppose γgh(G) = n. Suppose 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 with C ′ 6= 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 6= Kn. Let u, v ∈ V (G) such that dG(u, v) = 2 and let [u, p, v] be a u-v G. Salasalan, S. Canoy, Jr. / Eur. J. Pure Appl. Math, 14 (1) (2021), 112-125 115 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). Let v ∈ V (G) = V (G) and 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. 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), that is, az ∈ E(G) for every z ∈ NG(v). This shows that (ii) holds. For the converse, suppose first that (i) holds. 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. Thus, γgh(G) = n. Next, suppose that (ii) holds. Then every component of G is complete. Since V (G) = V (G) is the only hop dominating set of G, it follows that V (G) is the only global hop dominating set of G. Therefore,γgh(G) = n. The next result is a consequence of Theorem 2. Corollary 1. γgh(Kn) = γgh(K1,n−1) = n for all integer n ≥ 2. A set S ⊆ V (G) is a pairwise non-dominating set of G if for each v ∈ V (G) \ S, there exists vertex w ∈ S ∩NG(v) such that NG({w, v}) 6= V (G). A set S ⊆ V (G) is a pairwise and pointwise non-dominating (ppnd) set of G if it is both a pairwise non-dominating and pointwise non-dominating set of G. The minimum cardinality of a ppnd set of G is denoted by γppnd(G). Any pairwise and pointwise non-dominating set of G with cardinality equal to γppnd(G) is called a γppnd-set of G. Remark 2. A pairwise non-dominating set of G is a dominating set of G. Theorem 3. Let G be any graph of order n. Then 1 ≤ ppnd(G) ≤ n. Moreover, (i) γppnd(G) = 1 if and only if G = K1, (ii) γppnd(G) = 2 if and only if one of the following statements holds: (a) G = K2 (b) G = K2 (c) There exist non-adjacent vertices x, y ∈ V (G) such that NG(x) ∩ NG(y) = ∅ and NG[x] ∪NG[y] = V (G). (d) There exist adjacent vertices x, y ∈ V (G) such that NG(x)∩NG(y) = ∅, NG(x)∪ NG(y) = V (G), and for each v ∈ NG(x) \ {y} and w ∈ NG(y) \ {x}, there exist p ∈ NG(y) \NG(v) and q ∈ NG(x) \NG(w). G. Salasalan, S. Canoy, Jr. / Eur. J. Pure Appl. Math, 14 (1) (2021), 112-125 116 (iii) γppnd(G) = n if and only if G = Kn or G is connected such that NG({u, v}) = V (G) for each pair of adjacent vertices u, v ∈ V (G). Proof. Clearly, by definition, a pairwise and pointwise non-dominating set of G is nonempty. Thus, ppnd(G) ≥ 1. Also, since V (G) is a pairwise and pointwise non- dominating set of G, it follows that γppnd(G) ≤ n. (i) Next, suppose that γppnd(G) = 1, say S = {v} is a γppnd-set of G. If such a vertex outside S exists, then this would require two distinct vertices from S to satisfy the property of S. This forces us to conclude that G = K1. Further, since γppnd(K1) = 1, (i) holds. (ii) Suppose now that γppnd(G) = 2, say S = {x, y} is a γppnd-set of G. If n = 2, then G = K2 or G = K2. Suppose n ≥ 3 and assume first that xy /∈ E(G). Since S is a ppnd set of G, NG(x) ∩ NG(y) = ∅ and NG[x] ∪ NG[y] = V (G). Hence, (c) holds. Suppose xy ∈ E(G). Again, since S a ppnd set of G, NG(x) ∩ NG(y) = ∅ and NG(x) ∪ NG(y) = V (G). Let v ∈ NG(x) \ {y}. Since NG({x, v}) 6= V (G), there exists p ∈ V (G) \ NG({x, v}). Since NG(x) ∩ NG(y) = ∅, it follows that p ∈ NG(y) \ NG(v). Similarly, for each w ∈ NG(y) \ {x}, there exists q ∈ NG(x) \ NG(w), showing that (d) holds. For the converse, suppose first that G = K2 or G = K2. Then, clearly, γppnd(G) = 2. Next, suppose that (c) holds. Let S = {x, y} and let v ∈ V (G)\S. By assumption, we may assume that v ∈ NG(x) \NG(y). Since y ∈ V (G) \NG({x, v}), NG({x, v}) 6= V (G). Thus, S is a ppnd set of G. Since G 6= K1, it follows that S is a γppnd-set, i.e., γppnd(G) = |S| = 2. Finally, suppose that (d) holds. Let S′ = {x, y} and let v ∈ V (G) \ S. Assume, without loss of generality, that v ∈ NG(x). By assumption, there exists p ∈ NG(y) \NG(v). This implies that p /∈ NG({x, v}). Therefore, S is a γppnd-set of G, implying that γppnd(G) = 2. This proves statement (ii). (iii) Suppose γppnd(G) = n. Suppose first that G is disconnected. Suppose further that G 6= Kn. Then G has a non-trivial component C. Hence, there exist distinct vertices x, y ∈ V (C) such that xy ∈ V (G). Let Sx = V (G) \ {x}. Then y ∈ S ∩NG(x). Since G is disconnected, NG(x, y) 6= V (G) and there exists w ∈ S \NG(x). Hence, S is a ppnd set of G and γppnd(G) ≤ |S| = n− 1, a contradiction. Therefore, G = Kn. Next, suppose that G is connected. Suppose there exist distinct adjacent vertices u, v ∈ V (G) such that NG({u, v}) 6= V (G), say w ∈ V (G) \ NG({u, v}). Let Su = V (G) \ {u}. Then v, w ∈ S, uw /∈ E(G), uv ∈ E(G), and NG({u, v}) 6= V (G). This implies that S is a pairwise and pointwise non-dominating set of G. Hence, γppnd(G) ≤ |S| = n − 1, a contradiction. Therefore, NG({u, v}) = V (G) for each pair of adjacent vertices u, v ∈ V (G). For the converse, suppose first that G = Kn. Then, clearly, S = V (G) is the only pairwise and pointwise non-dominating set of G. Thus, γppnd(G) = n. Next, suppose that G is connected and satisfies the condition that NG({u, v}) = V (G) for each pair of adjacent vertices u, v ∈ V (G). Let S be a γppnd-set and suppose that there exists w ∈ V (G) \ S. Then there exists q ∈ S ∩NG(w) such that NG({q, w}) 6= V (G), contrary to our assumption. Therefore, S = V (G) and γppnd(G) = n. G. Salasalan, S. Canoy, Jr. / Eur. J. Pure Appl. Math, 14 (1) (2021), 112-125 117 Theorem 4. Let G and H be any two graphs. A set S ⊆ V (G + H) is a global hop dominating set of G + H if and only if S = SG ∪ SH and SG and SH are pairwise and pointwise non-dominating sets of G and H, respectively. Proof. Suppose S is a global hop dominating set of G+H. Let SG = S ∩ V (G) and SH = S ∩ V (H). Since S is a hop dominating set of G + H, SG 6= ∅ and SH 6= ∅. Let v ∈ V (G) \ SG. Since S is a hop dominating set of G+H, there exists u ∈ SG such that dG+H(u, v) = 2. This implies that uv /∈ E(G). Now, since S is also a hop dominating set of G+H = G ∪ H, there exists w ∈ SG such that dG+H(v, w) = dG(v, w) = 2. This implies that vw ∈ E(G) and there exists z ∈ V (G) such that z ∈ NG(v) ∩ NG(w). Thus, z /∈ NG({v, w}), showing that NG({v, w}) 6= V (G). Therefore, SG is a pairwise and pointwise non-dominating set of G. Similarly, SH is a pairwise and pointwise non- dominating set of H. For the converse, suppose that S = SG∪SH and SG and SH are pairwise and pointwise non-dominating sets of G and H, respectively. Let v ∈ V (G + H) \ S. Suppose, without loss of generality, that v ∈ V (G)\SG. Since SG is a pairwise and pointwise non-dominating set of G, there exist u,w ∈ SG ⊆ S such that uv /∈ E(G), wv ∈ E(G), and NG({w, v}) 6= V (G). It follows that dG+H(u, v) = 2 and dG+H(w, v) = dG(w, v) = 2. Thus, S is a global dominating set of G+H. The next result is immediate from Theorem 4 and Theorem 3(iii). Corollary 2. Let G and H be any two graphs. Then γgh(G+H) = γppnd(G)+γppnd(H). In particular, (i) γgh(Kn +H) = n+ γppnd(H) for all integer n ≥ 1, and (ii) γgh(Km,n) = m+ n for all positive integers m and n. The corona of graphs G and H, denoted by G ◦H, is the graph obtained from G by taking a copy Hv of H and forming the join 〈v〉+Hv = v +Hv for each v ∈ V (G). Theorem 5. Let G be a connected non-trivial graph and let H be any graph. A set C ⊆ V (G◦H) is a global hop dominating set of G◦H if and only if C = A∪ (∪v∈V (G)Sv), where A ⊆ V (G), Sv ⊆ V (Hv) for each v ∈ V (G) and satisfy the following properties: (i) For each w ∈ V (G) \ A, there exists xw ∈ A with dG(w, xw) = 2 or there exists y ∈ V (G) ∩NG(w) with Sy 6= ∅. (ii) Sv is a dominating set of Hv for each v ∈ NG(A) \A. (iii) Sv is a pointwise non-dominating set of Hv for each v ∈ A \NG(A). (iv) Sv is a dominating pointwise non-dominating set of Hv for each v ∈ V (G) \NG[A]. G. Salasalan, S. Canoy, Jr. / Eur. J. Pure Appl. Math, 14 (1) (2021), 112-125 118 Proof. Suppose C is a global hop dominating set of G ◦H and let A = C ∩ V (G). Let Sv = C ∩ V (Hv) for each v ∈ V (G). Then A ⊆ V (G), Sv ⊆ V (Hv) for each v ∈ V (G), and C = A ∪ (∪v∈V (G)Sv). Now, since C is a hop dominating set of G, (i) holds. Next, let v ∈ V (G) and consider the following cases: Case 1: v ∈ NG(A) \A Let x ∈ V (Hv) \ Sv. Since C is hop dominating set of G ◦H, there exists y ∈ C such that dG◦H(x, y) = 2. Since v /∈ A and V (G ◦H) \ V (v + Hv) ⊆ NG◦H(x), it follows that y ∈ Sv. Thus, y ∈ Sv ∩ NHv(x), showing that Sv is a dominating set of Hv. Therefore, (ii) holds. Case 2: v ∈ A \NG(A) Let w ∈ A \NG(A) and let q ∈ V (Hv) \Sv. Since C is a hop dominating set of G ◦H, there exists u ∈ C such that dG◦H(q, u) = 2. By assumption, u /∈ A. Thus, u ∈ Sv and qu /∈ E(Hv). Therefore Sv is a pointwise non-dominating set of Hv, showing that (iii) holds. Case 3: v ∈ V (G) \NG[A] Since v /∈ A and C is a hop dominating set of G, similar arguments in Case 1 will show that Sv is a dominating set of Hv. Further, since v /∈ NG(A), the arguments in Case 2 can be used to show that Sv is a pointwise non-dominating set of Hv, showing that (iv) holds. For the converse, suppose that C has the given form and satisfies properties (i), (ii), (iii), and (iv). Next, let z ∈ V (G ◦H) \ C = V (G ◦H) \ C and let v ∈ V (G) such that z ∈ V (v +Hv). Consider the following cases: Case 1. z = v Then there exists h ∈ C such that dG◦H(z, h) = 2, by (i). Now, from the assumption that (ii) and (iv) hold, it follows that Sz 6= ∅. Pick any p ∈ Sz and y ∈ V (Hw), where w ∈ V (G) ∩NG(z). Then zy, yp ∈ E(G ◦H); hence, dG◦H(z, p) = 2. Case 2. z 6= v Then z ∈ V (Hv) \ Sv. If v ∈ NG(A), then dG◦H(z, a) = 2 for a ∈ A ∩ NG(v). If v /∈ NG(A), then there exists b ∈ Sv ⊂ C such that dG◦H(z, b) = 2 by (iii) and (iv). Next, suppose first that v ∈ A. Pick any w ∈ V (G) \ {v} and let p ∈ V (Hw). Then p ∈ NG◦H(z) ∩ NG◦H(v). Thus, dG◦H(z, v) = 2. Suppose now that v /∈ A. By (ii) and (iv), Sv is a dominating set of Hv. It follows that there exists q ∈ Sv ∩ NHv(z). Pick any u ∈ V (G) \ {v}. Then u ∈ NG◦H(z) ∩NG◦H(q). Hence, there exists q ∈ C such that dG◦H(z, q) = 2. Accordingly, C is a hop dominating set of G◦H and G ◦H, showing that C is a global hop dominating set of G ◦H. Corollary 3. Let G be a connected non-trivial graph and let H be any graph. Then γgh(G ◦H) = |V (G)|. Proof. Let A = V (G) and set Sv = ∅ for each v ∈ V (G). Then C = A = A ∪ (∪v∈V (G)Sv) is a global hop dominating set of G by Theorem 5. Hence, γgh(G ◦ H) ≤ |C| = |V (G)|. G. Salasalan, S. Canoy, Jr. / Eur. J. Pure Appl. Math, 14 (1) (2021), 112-125 119 Next, let C0 be a γgh-set of G◦H. Then C0 = A0∪(∪v∈V (G)Rv), where A0 ⊆ V (G) and Rv ⊆ V (Hv) for each v ∈ V (G) and satisfy conditions (i), (ii), (iii), and (iv) of Theorem 5. Since C0 is a γgh-set of G ◦H, it follows that Rv = ∅ for all v ∈ D1 = A0∩NG(A0). From conditions (ii), (iii), and (iv), we find that |Rv| ≥ 1 for each v ∈ D2 = V (G) \D1. Thus, γgh(G ◦H) = |C0| = |A0|+ ∑ v∈D2 |Rv| ≥ |A0|+ |D2| = |V (G)|+ (|A0| − |D1|) ≥ |V (G)|. Therefore, γgh(G ◦H) = |V (G)|. The lexicographic product of graphs G and H, denoted by G[H], is the graph with vertex set V (G[H]) = V (G)× V (H) such that (v, a)(u, b) ∈ E(G[H]) if and only if either uv ∈ E(G) or u = v and ab ∈ E(H). Note that every non-empty subset C of V (G) × V (H) can be expressed as C = ∪x∈S [{x} × Tx], where S ⊆ V (G) and Tx ⊆ V (H) for each x ∈ S. Theorem 6. Let G and H be connected non-trivial graphs. A subset C = ∪x∈S [{x} × Tx] of V (G[H]) is a global hop dominating set of G[H] if and only if the each following conditions holds: (i) S is both a dominating and a hop dominating set of G. (ii) Tx is a pointwise non-dominating set of H for each x ∈ S with |NG(x, 2) ∩ S| = 0. (iii) Tx is a dominating set of H for each x ∈ S with S∩NG(x) = ∅ or [V (G)\NG(x)]∩ [V (G) \ NG(y)] = ∅ for each y ∈ S ∩ NG(x). If, in addition, NG[x] = V (G), then Tx is a pairwise non-dominating set of H. (iv) For each z ∈ V (G)\S, there exists y ∈ S∩NG(z) such that [V (G)\NG(z)]∩ [V (G)\ NG(y)] 6= ∅. Proof. Suppose C is a global hop dominating set of G[H]. Let u ∈ V (G) \ S and pick any a ∈ V (H). Since C is a hop dominating set of G[H] and (u, a) /∈ C, there exists (y, b) ∈ C such that dG[H]((u, a)(y, b)) = 2. This implies that y ∈ S and dG(u, y) = 2. Also, since C is a hop dominating set of G[H] and (u, a) /∈ C, there exists (z, c) ∈ C such that d G[H] ((u, a)(z, c)) = 2. It follows that z ∈ S and dG(u, z) = 1. Hence, S is both a dominating and a hop dominating set of G, showing that (i) holds. Let x ∈ S. Suppose that |NG(x, 2) ∩ S| = 0. Then Tx is a pointwise non-dominating set of H. Hence, (ii) holds. Suppose now that S∩NG(x) = ∅ or [V (G)\NG(x)]∩ [V (G)\ NG(y)] = ∅ for each y ∈ S ∩NG(x). Let p ∈ V (H) \ Tx. Since (x, p) ∈ V (G[H]) \C an C is a hop dominating set of G[H], there exists (w, q) ∈ C such that d G[H] ((x, p)(w, q)) = 2, that is, dG[H]((x, p)(w, q)) = 1. If S ∩ NG(x) = ∅, then w = x and q ∈ Tx ∩ NH(p), implying that Tx is a dominating set of H. Suppose S∩NG(x) 6= ∅. Suppose further that w 6= x. Then w ∈ S ∩NG(x). By assumption, [V (G) \NG(x)]∩ [V (G) \NG(w)] = ∅. Let [(x, p), (u, t), (w, q)] be an (x, p)-(w, q) geodesic in G[H]. Suppose u 6= x. Since xu ∈ E(G), u ∈ V (G) \ NG(x). The assumption would now imply that u /∈ V (G) \ NG(w). Thus, u ∈ NG(w), a contradiction. Hence, u = x. This, however, is not possible because xw ∈ E(G). Therefore, w = x, implying that q ∈ Tx ∩NH(p). Hence, Tx is a dominating G. Salasalan, S. Canoy, Jr. / Eur. J. Pure Appl. Math, 14 (1) (2021), 112-125 120 set of H. Finally, suppose that NG[x] = V (G). Then u = x and t ∈ NH(p) ∩ NH(q). It follows that t /∈ NH [{p, q}]. Thus, Tx is a pairwise non-dominating set of H. Therefore, (iii) holds. Now let z ∈ V (G)\S. Choose any b ∈ V (H). Since C is a hop dominating set of G[H], there exists (y, c) ∈ C such that d G[H] ((z, b)(y, c)) = 2, that is, dG[H]((z, b)(y, c)) = 1. Hence, y ∈ S ∩ NG(z). Let [(z, b), (s, d), (y, c)] be a (z, b)-(y, c) geodesic in G[H]. Then s ∈ [V (G) \NG(z)] ∩ [V (G) \NG(y)], showing that (iv) holds. For the converse, suppose that C satisfies properties (i), (ii), (iii), and (iv). By (i) and (ii), C is a hop dominating set of G[H]. Let (v, a) ∈ V (G[H]) \ C and consider the following cases: Case 1. v /∈ S By (iv), let y ∈ S ∩ NG(v) and let u ∈ [V (G) \ NG(v)] ∩ [V (G) \ NG(y)] = ∅. Let p ∈ Ty. Then (y, p) ∈ C and [(v, a), (u, a), (y, p)] is a (v, a)-(y, p) geodesic in G[H]. Thus, d G[H] ((v, a)(y, p)) = 2. Case 2. v ∈ S Suppose S∩NG(v) 6= ∅ and [V (G)\NG(v)]∩[V (G)\NG(y)] 6= ∅ for some y ∈ S∩NG(v). Choose any q ∈ Ty and let w ∈ [V (G) \ NG(v)] ∩ [V (G) \ NG(y)]. Then (y, q) ∈ C and [(v, a), (w, a), (y, q)] is a (v, a)-(y, q) geodesic in G[H]. Thus, d G[H] ((v, a)(y, q)) = 2. Next, suppose that S∩NG(v) = ∅ or [V (G)\NG(v)]∩ [V (G)\NG(y)] = ∅ for all y ∈ S∩NG(v). Suppose NG[v] = V (G). Then Tv is a pairwise non-dominating set of H by (iii). Hence, there exists d ∈ Tv∩NH(a) such that NH({a, d}) 6= V (H). This implies that (v, d) ∈ C and there exists t ∈ V (H) \NH({a, d}). Hence, [(v, a), (v, t), (v, d)] is a (v, a)-(v, d) geodesic in G[H], that is, d G[H] ((v, a), (v, d)) = 2. SupposeNG[v] 6= V (G). By (iii), Tv is a dominating set of H. Again, let d ∈ Tv ∩ NH(a) and pick w ∈ V (H) \ NG[v]. Then (v, d) ∈ C and [(v, a), (w, a), (v, d)] is a (v, a)-(v, d) geodesic in G[H]. Thus, d G[H] ((v, a), (v, d)) = 2. Therefore, C is a hop dominating set of G[H]. Accordingly, C is a global hop domi- nating set of G[H]. A set S ⊆ V (G) is said to be dominating complement-neighborhood intersecting (dcni) (resp. total dominating complement-neighborhood intersecting (tdcni)) set of a graph G if for each v ∈ V (G) \ S (resp. for each v ∈ S), there exists w ∈ S ∩ NG(v) such that (V (G) \NG(v)) ∩ (V (G) \NG(w)) 6= ∅. Let γhcni(G) = min{|S| : S is a dcni hop dominating set of G}, and γtcni(G) = min{|S| : S is a tdcni set of G}. Any dcni hop dominating set of G with cardinality γhcni(G) is called a γhcni-set of G and any tdcni set of G with cardinality γtcni(G) is called a γtcni-set of G. Observe that for any graph G, the vertex set V (G) is a dominating complement- neighborhood intersecting and hop dominating set of G. Also, if G1 is the graph obtained from the cycle C4 = [a, b, c, d, a] by adding the edges av and bw, then S = {a, b} is a dcni G. Salasalan, S. Canoy, Jr. / Eur. J. Pure Appl. Math, 14 (1) (2021), 112-125 121 hop dominating set of G1. Proposition 1. Let G be graph without isolated vertices. (i) If G is disconnected, then G admits a tdcni set. (ii) If G admits a tdcni set, then 3 ≤ γtcni(G) ≤ |V (G)|. (iii) If γt(G) 6= 2, then G admits a tdcni set. If, in addition, G has at most one vertex of degree one, then γtcni(G) ≤ |V (G)| − 1. Proof. (i) Suppose G is disconnected and let S = V (G). Let v ∈ S. Since G has no isolated vertices, there exists w ∈ S ∩NG(v). Let C1 and C2 be distinct components of G with w, v ∈ C1. Pick any z ∈ C2. Then z ∈ (V (G) \ NG(v)) ∩ (V (G) \ NG(w)). Hence, S = V (G) is a tdcni set of G. (ii) Suppose G admits a tcnid set. Since a tdcni set is a total dominating set, it follows that 2 ≤ γtcni(G) ≤ n. Suppose γtcni(G) = 2, say S = {x, y} is a γtcni-set of G. Since S is a dominating set, V (G) \ S ⊆ NG({x, y}). Hence, (V (G) \NG(x))∩ (V (G) \NG(y)) = ∅, contrary to the assumption that S is a tdcni set. Thus, 3 ≥ γtcni(G). (iii) Suppose γt(G) 6= 2. Let v ∈ V (G) and let w ∈ V (G) ∩ NG(v). By assumption, NG({v, w} 6= V (G). This implies that there exists y ∈ (V (G) \NG(v))∩ (V (G) \NG(w)), showing that V (G) is a tdcni set of G. Suppose further that G has at most one vertex of degree one. Let v ∈ V (G) such that δ(G) = degG(v) and let S = V (G) \ {v}. Note that if degG(v) = 1, then degG(w) ≥ 2 for all w ∈ V (G) \ {v}. Let u ∈ S ∩NG(v). Since γ(G) 6= 2, (V (G) \ NG(v)) ∩ (V (G) \ NG(w)) 6= ∅. Let z ∈ S. Since degG(z) ≥ 2, there exists y ∈ S ∩NG(z). Again, since γ(G) 6= 2, (V (G) \NG(z))∩ (V (G) \NG(y)) 6= ∅. This implies that S is a tdcni set and γtcni(G) ≤ |S| = |V (G)| − 1. Corollary 4. Let G and H be non-trivial connected graphs. (i) If γ(G) = 1, then γgh(G[H]) ≤ γhcni(G).γppnd(H). (ii) If γ(G) 6= 1, then γgh(G[H]) ≤ γhcni(G).γpnd(H). Proof. Let S be a γhcni-set of G. Let D1 and D2 be, respectively, a γppnd-set and γpnd-set of H. Set Tx = D for each x ∈ S and Rx = D2. If γ(G) = 1, then C1 = ∪x∈S [{x} × Tx] = S ×D1 is a global hop dominating set of G[H] by Theorem 6. Hence, γgh(G[H]) ≤ |C1| = |S||D1| = γhcni(G).γppnd(H), proving that (i) holds. If γ(G) 6= 1, then C2 = ∪x∈S [{x} × Rx] = S × D2 is a global hop dominating set of G[H] by Theorem 6. Hence, γgh(G[H]) ≤ |C2| = |S||D2| = γhcni(G).γpnd(H), showing that (ii) holds. Remark 3. The bounds in Corollary 4 are sharp. G. Salasalan, S. Canoy, Jr. / Eur. J. Pure Appl. Math, 14 (1) (2021), 112-125 122 To see this, let G1 be the graph obtained from the cycle C4 = [a, b, c, d, a] by adding the edges av and bw, and let H = P3. As pointed out earlier, S = {a, b} is a dcni hop dominating set of G1. In fact, γhcni(G1) = |S| = 2. Now, γpnd(H) = 2 by Theorem 3(iii). It can easily be verified that γgh(G[H]) = 4 = γhcni(G).γpnd(H). Also, γgh(P4[P2]) = γhcni(P4).γpnd(P2) = 2(2) = 4 and γgh(P2[P2]) = γgh(K4) = γhcni(P4).γppnd(P2) = 2(2) = 4. The Cartesian product of graphs G and H, denoted by G�H, is the graph with vertex set V (G�H) = V (G) × V (H) such that (v, p)(u, q) ∈ E(G�H) if and only if uv ∈ E(G) and p = q ∈ E(H)] or u = v and pq ∈ E(G). Theorem 7. Let G and H be connected non-trivial graphs. A subset C = ∪x∈S [{x}×Tx] of V (G�H) is a global hop dominating set of G�H if and only if the following conditions hold: (i) For each x ∈ V (G) \ S and for each p ∈ V (H), (a) there exists y ∈ S ∩ NG(x) such that Ty ∩ NH(p) 6= ∅ or there exists z ∈ S ∩NG(x, 2) such that p ∈ Tz, and (b) there exists w ∈ S ∩ NG(x) such that p ∈ Tw and [NH [p] 6= V (H) or (V (G) \ NG(x)) ∩ (V (G) \NG(w)) 6= ∅]. (ii) For each v ∈ S and for each p ∈ V (H) \ Tv, the following statements are satisfied: (c) NH(p, 2)∩ Tv 6= ∅ or there exists y ∈ S ∩NG(v) such that Ty ∩NH(p) 6= ∅, or there exists z ∈ S ∩NG(v, 2) such that p ∈ Tz. (d) NH(p) ∩ Tv 6= ∅ and [V (G) \ NG[v] 6= ∅ or |V (H)| ≥ 3] or there exists u ∈ S ∩NG(v) such that p ∈ Tu and [NH [p] 6= V (H) or (V (G) \NG(v)) ∩ (V (G) \ NG(u)) 6= ∅]. Proof. Suppose C is a global hop dominating set of G�H. Let x ∈ V (G) \ S and let p ∈ V (H). Since C is a hop dominating set of G�H and (x, p) /∈ C, there exists (y, q) ∈ C such that dG�H((x, p)(y, q)) = 2. Since y ∈ S, x 6= y. If xy ∈ E(G), then pq ∈ E(H). Hence, q ∈ Ty∩NH(p). So suppose that y /∈ NG(x). Since dG�H((x, p)(y, q)) = 2, it follows that y ∈ NG(x, 2) and p = q. Hence, p ∈ Ty, showing that (a) holds. Now, since C is also a hop dominating set of G�H, there exists (w, t) ∈ C such that dG�H((x, p)(w, t)) = 2. It follows that dG�H((x, p)(w, t)) = 1. This implies that w ∈ S ∩ NG(x) and p ∈ Tw. Now, if [(x, p), (z, s), (w, t)] is an (x, p)-(w, t) geodesic in G�H, then s ∈ V (H) \NH [p] or z ∈ ((V (G) \NG(x) ∩ (V (G) \NG(w)). This shows that (b) holds. Next, let v ∈ S and let p ∈ V (H) \ Tv. Since C is a hop dominating set of G�H and (v, p) /∈ C, there exists (y, q) ∈ C such that dG�H((v, p)(y, q)) = 2. Suppose y = v. Then dH(p, q) = 2 and so q ∈ NG(p, 2) ∩ Tv. Suppose y 6= v. If dG(y, v) = 1, then y ∈ S ∩NG(v) and dH(p, q) = 1, i.e. q ∈ Ty ∩NH(p). If dG(y, v) 6= 1, then dG(y, v) = 2, Hence, y ∈ S ∩NG(v, 2) and p = q, that is, p ∈ Ty. Thus, (b) holds. On the other hand, since C is also a hop dominating set ofG�H and (v, p) /∈ V (G�H)\ C, there exists (u, t) ∈ C such that dG�H((v, p)(u, t)) = 2. Again, this would imply G. Salasalan, S. Canoy, Jr. / Eur. J. Pure Appl. Math, 14 (1) (2021), 112-125 123 that dG�H((v, p)(u, t)) = 1. If u = v, then t ∈ NH(p) ∩ Tv. Since dG�H((v, p)(u, t)) = dG�H((v, p)(v, t)) = 2, V (G) \ NG[v] 6= ∅ or |V (H)| ≥ 3. Suppose u 6= v. Then u ∈ S ∩ NG(v) and p ∈ Tu. Since dG�H((v, p)(u, t)) = 2, V (H) \ NH(p) 6= ∅ or (V (G) \ NG(v)) ∩ (V (G) \NG(u)) 6= ∅. For the converse, suppose that C satisfies properties (i) and (ii). Let (v, p) ∈ V (G[H])\ C and consider the following cases: Case 1. v /∈ S By the assumption that (a) of (i) holds, suppose first that there exists y ∈ S ∩ NG(x) such that Ty ∩ NH(p) 6= ∅. Let q ∈ Ty ∩ NH(p) 6= ∅. Then (y, q) ∈ C and dG�H((v, p)(y, q)) = dG(v, y) + dH(p, q) = 2. Next, suppose that there exists z ∈ S ∩NG(v, 2) such that p ∈ Tz. Then (z, p) ∈ C and dG�H((v, p)(z, p)) = dG(v, z) = 2. Since (b) of (i) also holds, suppose that there exists w ∈ S ∩NG(v) such that p ∈ Tw. Then (w, p) ∈ C ∩NG�H((v, p)). If NH [p] 6= V (H), we may pick any s ∈ V (H) \NH [p]. Then (w, s) /∈ NG�H((v, p))∪NG�H((w, p)). It follows that [(v, p), (w, s), (w, p)] is a (v, p)- (w, p) geodesic inG�H. Thus, dG�H((v, p)(w, p)) = 2. Instead ofNH(p) 6= V (H), suppose that (V (G)\NG(x))∩(V (G)\NG(w)) 6= ∅], say u ∈ (V (G)\NG(x))∩(V (G)\NG(w)). Then [(v, p), (u, p), (w, p)] is a (v, p)-(w, p) geodesic in G�H, implying that dG�H((v, p)(w, p)) = 2. Case 2. v ∈ S Utilizing (c) of (ii), suppose first that NH(p, 2)∩Tv 6= ∅. Let q ∈ NH(p, 2)∩Tv. Then (v, q) ∈ C and dG�H((v, p)(v, q)) = dH(p, q) = 2. Suppose there exists y ∈ S ∩NG(v) such that Ty∩NH(p) 6= ∅. Then (y, t) ∈ C and dG�H((v, p)(y, t)) = 2, where t ∈ Ty∩NH(p). If there exists z ∈ S ∩NG(v, 2) such that p ∈ Tz, then (z, p) ∈ C and dG�H((v, p)(z, p)) = 2. Now, using (d) of (ii), assume that NH(p) ∩ Tv 6= ∅, say a ∈ NH(p) ∩ Tv. Then (v, a) ∈ C. If there exists w ∈ V (G) \ NG[v], then [(v, p), (w, p), (v, a)] is a (v, p)-(v, a) geodesic in G�H. Thus, dG�H((v, p)(v, a)) = 2. If |V (H)| ≥ 3, then we may pick any b ∈ V (H) \ {a, p}. Let z ∈ NG(v). Then [(v, p), (z, b), (v, a)] is a (v, p)-(v, a) geodesic in G�H. Hence, dG�H((v, p)(v, a)) = 2. Next, assume that there exists u ∈ S ∩ NG(v) such that p ∈ Tu. Then (u, p) ∈ C. If V (H) \ NH(p), then [(v, p), (u, l), (u, p)] is a (v, p)-(u, p) geodesic in G�H. This implies that dG�H((v, p)(u, p)) = 2. If there exists z ∈ (V (G) \NG(v)) ∩ (V (G) \NG(u)), then [(v, p), (z, p), (u, p)] is a (v, p)-(u, p) geodesic in G�H, implying that dG�H((v, p)(u, p)) = 2. Therefore, C is a hop dominating set of G�H and G�H. Accordingly, C is a global hop dominating set of G�H. Corollary 5. Let G and H be non-trivial connected graphs. (i) If γ(H) = 1, then γgh(G�H) ≤ |V (H)|.γtcni(G). (ii) If γ(H) 6= 1, then γgh(G�H) ≤ |V (H)|.γt(G). Proof. Let S be a γtcni-set of G and let Tx = V (H) for all x ∈ S. Let C = ∪x∈S [{x}× Tx] = S×V (H). If γ(H) = 1, then C is a global hop dominating set of G�H by Theorem 7. Thus, γgh(G�H) ≤ |C| = |V (H)|.γtcni(G). REFERENCES 124 Next, let S′ be a γt-set of G and let Rx = V (H) for all x ∈ S′. Let C ′ = ∪x∈S [{x} × Rx] = S×V (H). If γ(H) 6= 1, then C ′ is a global hop dominating set of G�H by Theorem 7. This implies that γgh(G�H) ≤ |C ′| = |V (H)|.γt(G). 3. Conclusion The global hop dominating sets in the join, corona, lexicographic product, and the Cartesian product of two graphs have been characterized. From these characterizations, we determined either the exact values or upper bounds of the global hop domination numbers of the corresponding graphs. Acknowledgements The authors would like to thank the referees for reviewing the paper and for pointing out some (minor) errors in the original manuscript. Also, we would like to thank the Department of Science and Technology - Accelerated Science and Technology Human Re- source Development Program (DOST-ASTHRDP), Philippines for funding this research. References [1] S. Ayyaswamy, B. Krishnakumari, B. Natarjan, and Y. Venkatakrishnan. Bounds on the hop domination number of a tree. Proceedings-Mathematical Sciences, 125(4):449– 455, 2015. [2] 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. [3] 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. [4] W. Desormeaux, P. Gibson, and T. Haynes. Bounds on the global domination number. Quaestiones Mathematicae, 38(4):563–572, 2015. [5] T. Haynes, S. Hedetniemi, and P. Slater. Domination in Graphs, Advanced Topics. Marcell Dekker, New York, USA, 1998. [6] T. Haynes, S. Hedetniemi, and P. Slater. Fundamentals of Domination in Graphs. Marcell Dekker, New York, USA, 1998. [7] M. Henning and N. Rad. On 2-step and hop dominating sets in graphs. Graphs and Combinatorics, 33(4):913–927, 2017. [8] G. Mahadevan and V. Vijayalakshmi. Clone hop domination number of a graph. Journal of Discrete Mathematical Sciences and Cryptography, 22(5):719–729, 2019. REFERENCES 125 [9] R. Mollejon and S. Jr. Canoy. Double hop dominating sets in graphs. Discrete Mathematics, Algorithms and Applications, 2020, https://doi.org/10.1142/S1793830921500579. [10] C. Natarajan and S. Ayyaswamy. Hop domination in graphs II. Versita, 23(2):187– 199, 2015. [11] 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.