EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS Vol. 15, No. 2, 2022, 467-477 ISSN 1307-5543 – ejpam.com Published by New York Business Global Hop Independent Sets in Graphs Javier A. Hassan1,∗, Sergio R. Canoy, Jr.1, Alkajim A. Aradais2 1 Department of Mathematics and Statistics, College of Science and Mathematics, Center for Graph Theory, Algebra and Analysis-PRISM, MSU-Iligan Institute of Technology, 9200 Iligan City, Philippines 2 Integrated Laboratory School, College of Education, Mindanao State University-TCTO, Tawi-Tawi, Philippines Abstract. Let G be an undirected graph with vertex and edge sets V (G) and E(G), respectively. A set S ⊆ V (G) is a hop independent set of G if any two distinct vertices in S are not at a distance two from each other, that is, dG(v, w) 6= 2 for any distinct vertices v, w ∈ S. The maximum cardinality of a hop independent set of G, denoted by αh(G), is called the hop independence number of G. In this paper, we show that the absolute difference of the independence number and the hop independence number of a graph can be made arbitrarily large. Furthermore, we determine the hop independence numbers of some graphs including those resulting from some binary operations of graphs. 2020 Mathematics Subject Classifications: 05C69 Key Words and Phrases: locating, stable, domination, join, corona 1. Introduction In this paper we explore a parameter that is, in some sense, defined in a similar way that the well-known independence number of a graph is. Indeed, while an independent set of graph requires that no two distinct vertices in the set are at distance one from each other, the concept that we will be dealing with here imposes the condition that no two distinct vertices in the set are at distance two from each other. The motivation of introducing the concept is the ever increasing number of studies on hop domination and some of its variations. In fact, it can be shown that every maximum hop independent set of a graph is a hop dominating set. Consequently, the hop domination number of a graph is at most equal to the hop independence number of the graph. The concept of hop domination was introduced and studied by Natarajan and Ayyaswamy in [4]. The concept and some of its variants are also studied in [1], [2], ∗Corresponding author. DOI: https://doi.org/10.29020/nybg.ejpam.v15i2.4350 Email addresses: javier.hassan@g.msuiit.edu.ph (J. Hassan), sergio.canoy@g.msuiit.edu.ph (S. Canoy, Jr.), alkajim.aradais@g.msuiit.edu.ph (A. Aradais) https://www.ejpam.com 467 © 2022 EJPAM All rights reserved. J. Hassan, S. Canoy, Jr., A. Aradais / Eur. J. Pure Appl. Math, 15 (2) (2022), 467-477 468 [3], [5], [6], [7], [8], and [9]. Alongside other previously defined parameters in a graph, the hop independence number of a graph may be used to give bounds on some hop-domination related parameters. Moreover, this newly defined concept may be utilized to introduce some concepts (say, a variant of hop domination) in the future. 2. Terminology and Notation For any two vertices u and v in an undirected connected graph G, the distance dG(u, v) is the length of a shortest path joining u and v. Any u-v path of length dG(u, v) is called a u-v geodesic. The open neighborhood of a point u is the set NG(u) consisting of all points v which are adjacent to u. The closed neighborhood of u is NG[u] = NG(u) ∪ {u}. For any A ⊆ V (G), NG(A) = ⋃ v∈A NG(v) is called the open neighborhood of A and NG[A] = NG(A) ∪ A is called the closed neighborhood of A. The open hop neighborhood of a point u is the set N2 G(u) = {v ∈ V (G) : dG(v, u) = 2}. The closed hop neighborhood of u is N2 G[u] = N2 G(u) ∪ {u}. For any A ⊆ V (G), N2 G(A) = ⋃ v∈A N2 G(v) is called the open hop neighborhood of A and N2 G[A] = N2 G(A) ∪A is called the closed hop neighborhood of A. A set S ⊆ V (G) is a hop dominating set if N2 G[S] = V (G). The minimum cardinality of a hop dominating set of a graph G, denoted by γh(G), is called the hop domination number of G. A set S ⊆ V (G) is an independent set of G if no two pair of distinct vertices of S are adjacent. The maximum cardinality of an independent set of G, denoted by α(G), is called the independence number of G. Set S is a hop independent set of G if for any two distinct vertices v and w of S, dG(v, w) 6= 2. The maximum cardinality of a hop independent set of G, denoted by αh(G), is called the hop independence number of G. Any independent (hop independent) set with cardinality α(G) (resp. αh(G)) is referred to as a maximum independent set or α-set (resp. maximum hop independent set or αh-set) of G. A set S is clique of a graph G if the graph 〈S〉 induced by S is a complete graph. The maximum size or cardinality of a clique of G, denoted by ω(G), is called the clique number of G. Any clique in G with cardinality ω(G) is called an ω-set in G. 3. Results Proposition 1. Let G be any graph on n vertices. If S is a maximun hop independent set of G, then S is a hop dominating set. In particular, γh(G) ≤ αh(G). Proof. Let S be a maximun hop independent set of G and let v ∈ V (G) \ S. If dG(v, w) 6= 2 for all w ∈ S, then S ∪ {v} is a hop independent set of G, contradicting the maximality of S. Thus, there exists z ∈ S such that dG(v, z) = 2, showing that S is a hop dominating set of G. Therefore γh(G) ≤ αh(G). Theorem 1. Let G be any graph on n vertices. If S is a hop independent set of G, then every component of 〈S〉 is complete. Moreover, J. Hassan, S. Canoy, Jr., A. Aradais / Eur. J. Pure Appl. Math, 15 (2) (2022), 467-477 469 (i) αh(G) = n if and only if every component of G is complete; and (ii) for n ≥ 3, αh(G) = n − 1 if and only if all but a single component C of G are complete and C \ v is a complete graph for some vertex v ∈ V (C). Proof. Let S be a hop independent set of G. If some component C of 〈S〉 is not com- plete, then there exist distinct vertices x, y ∈ C such that dG(x, y) = dC(x, y) = 2. This, however, contradicts our assumption of S. Hence, every component of 〈S〉 is complete. (i) Now, if αh(G) = n, then V (G) is a hop independent set of G. By the first part, this would imply that every component of G is complete. Conversely, suppose that every component of G is complete. Then clearly, V (G) is a hop independent set of G. Thus, αh(G) = n. This proves (i). (ii) Suppose that αh(G) = n− 1. Then there exists v ∈ V (G) such that S = V (G) \ {v} is a hop independent set of G. Let Ω = {C1, C2, . . . , Ck} be the set consisting of the components of 〈S〉. Again, by the first part, every component Cj of 〈S〉 is complete. Now, by (i) and the assumption, it follows that G has a component C that is not complete. Hence, 〈{v}〉 is not a component of G; otherwise, C1, C2, . . . , Ck, 〈{v}〉 are the components of G which is not possible. This implies that there exists z ∈ S such that vz ∈ E(G). Let Cr be the component of 〈S〉 containing z. Since S is a hop independent set, vq /∈ E(G) for all q ∈ ∪j 6=rV (Cj). Let D = V (Cr) ∪ {v} and let C = 〈D〉. Then (Ω \ {Cr}) ∪ {C} contains all the components of G. Consequently, C is not complete and C \ v = Cr is complete. Next, suppose that all but a single component C of G are complete and C \ v is a complete graph for some vertex v ∈ V (C). Then αh(G ≤ n−1 by (i). Since S′ = V (G)\{v} is a hop independent set of G, it follows that αh(G) = n− 1. The next result is immediate from Theorem 1. Corollary 1. Let G be a connected graph on n vertices. Then (i) αh(G) = n if and only if G = Kn; and (ii) for n ≥ 3, αh(G) = n− 1 if and only if G 6= Kn and there exists v ∈ V (G) such that G \ v = Kn−1. Proposition 2. Let n be a positive integer. (i) There exists a connected graph G such αh(G)− α(G) = n. (ii) There exists a connected graph G such α(G)− αh(G) = n. Proof. For (i), consider G = Kn+1. Then α(G) = 1, and by Corollary 1, αh(G) = n+1. Hence, αh(G)− α(G) = n. J. Hassan, S. Canoy, Jr., A. Aradais / Eur. J. Pure Appl. Math, 15 (2) (2022), 467-477 470 For (ii), consider G = K1,n+2. Then α(G) = n + 2 and αh(G) = 2. Thus, α(G) − αh(G) = n. Note that Proposition 2 implies that given a positive integer n, there exists a connected graph G such that |α(G)−αh(G)| = n, i.e., the absolute difference of these two parameters can be made arbitrarily large. Theorem 2. Let a and b be positive integers such that 3 ≤ a ≤ b. Then (i) there exists a connected graph G such αh(G) = a and α(G) = b, and (ii) there exists a connected graph G′ such α(G′) = a and αh(G ′) = b. Proof. Suppose first that a = b. Consider the graph G in Figure 1. Clearly, S1 = {y1, y2, . . . , ya} is both an α-set and an αh-set of G. Hence, α(G) = αh(G) = a. ......... ........ ........ ........ ........ ........ ........ ........ ........ ... .................................... .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ... .................................... .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ... .................................... .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ... .................................... .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ... .................................... .................................... ................................................................................................................ ................................................................................................................ .................................... ................................................................................................................ .................................... y1 y2 y3 ya−1 ya x1 x2 x3 xa−1 xa . . . G Figure 1 Next, suppose that a < b and let m = b − a + 1. Consider the graph G in Figure 2. It can easily be verified that the set S1 = {y1, y2, . . . , ya−2, xa, z1} is an αh-set and S2 = {y1, . . . , ya−1, z1, . . . , zm} is an α-set of G. Thus, αh(G) = a and α(G) = b. ......... ........ ........ ........ ........ ........ ........ ........ ........ ... .................................... .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ... .................................... .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ... .................................... .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ... .................................... .................................... ................................................................................................................ ................................................................................................................ .................................... ................................................................................................................ .................................... ............ ........... ........... ........... ........... ........... .... .................................... .................................... ......................................... ...................... .................................... .................................... ....................................................................... .................................... .................................... y1 y2 y3 ya−1 x1 x2 x3 xa−1 xa z1 z2 zm . . . ... G Figure 2 (ii) Suppose a < b and let m = b−a+1. Consider the graph G′ in Figure 3. It can easily be verified that the set S = {y1, y2, . . . , ya−1, xa} is an α-set and S′ = {y1, . . . , ya−1, z1, . . . , zm} is an αh-set of G′. Thus, α(G′) = a and αh(G ′) = b. J. Hassan, S. Canoy, Jr., A. Aradais / Eur. J. Pure Appl. Math, 15 (2) (2022), 467-477 471 ......... ........ ........ ........ ........ ........ ........ ........ ........ ... .................................... .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ... .................................... .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ... .................................... .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ... .................................... .................................... ................................................................................................................ ................................................................................................................ .................................... ................................................................................................................ .................................... ............ ........... ........... ........... ........... ........... .... .................................... .................................... ................................................ ............................. .................................... .................................... ....................................................................... .................................... .................................... .......................................... .................................... .................................... .......... ......... ......... ......... ......... ......... ......... ... . ................................... .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ....... .................................... .................................... y1 y2 y3 ya−1 x1 x2 x3 xa−1 xa z1 z2 zm . . . ... G′ Figure 3 This proves the assertion. For any graph G, let δh(G) = min{|N2 G(v)| : v ∈ V (G)}. Theorem 3. For any graph G on n vertices, αh(G) ≤ n− δh(G). Proof. Let S be a maximum hop independent set of G and let v ∈ S. By definition, δh(G) ≤ |N2 G(v)|. Since S is a hop independent set of G and v ∈ S, N2 G(v) ⊆ V (G) \ S. Hence, δh(G) ≤ |N2 G(v)| ≤ n− |S| = n− αh(G). Therefore, αh(G) ≤ n− δh(G). The join of two graphs G and H, denoted by G + 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), v ∈ V (H)}. Theorem 4. Let G and H be graphs. Then S is a non-empty hop independent set of G+H if and only if one of the following statements holds: (i) S ∩ V (H) = ∅ and S ∩ V (G) is a clique in G. (ii) S ∩ V (G) = ∅ and S ∩ V (H) is a clique in H (iii) S ∩ V (G) and S ∩ V (G) are cliques in G and H, respectively. Proof. Suppose S is a hop independent set of G + H and let SG = S ∩ V (G) and SH = S ∩ V (H). Suppose SH = ∅. Then SG 6= ∅. Let a, b ∈ SG. Since S is a hop independent set of G + H, it follows that dG+H(a, b) = dG(a, b) 6= 2. This implies that dG(a, b) = 1, showing that SG is a clique in G. Hence, (i) holds. Similarly, (ii) holds. Next, suppose that SG 6= ∅ and SH 6= ∅. Then, clearly, SG and SH are cliques in G and H, respectively. The converse is clear. The next result is a consequence of Theorem 4. Corollary 2. Let G and H be graphs. Then αh(G +H) = ω(G) + ω(H). In particular, we have J. Hassan, S. Canoy, Jr., A. Aradais / Eur. J. Pure Appl. Math, 15 (2) (2022), 467-477 472 (i) αh(Kn +H) = n+ ω(H) for all n ≥ 1; (ii) αh(Wn) = αh(K1 + Cn) = 3 for all n ≥ 4; (iii) αh(Fn) = αh(K1 + Pn) = 3 for all n ≥ 1; and (iv) αh(K1,n) = αh(K1 +Kn) = 2 for all n ≥ 1. 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 non-trivial connected graph and let H be any graph. Then S is a hop independent set in G◦H if and only if S = A∪ (∪v∈V (G)Sv) and satisfies the following conditions: (i) A is a hop independent set in G. (ii) Sv is empty or a clique in Hv for each v ∈ V (G) \NG(A). (iii) Sv = ∅ for each v ∈ NG(A). Proof. Suppose S is a hop independent set in G ◦ H and let A = S ∩ V (G) and Sv = S ∩ V (Hv) for each v ∈ V (G). Since S is a hop independent set in G ◦ H, A is a hop independent set in G. This shows that (i) holds. Next, let v ∈ V (G). Suppose first that v ∈ V (G) \ NG(A). Suppose further that Sv 6= ∅. Clearly, if |Sv| = 1, then it is a clique. So suppose |Sv| ≥ 2 and let x, y ∈ Sv. Since S is a hop independent set, dG◦H(x, y) = dHv(x, y) 6= 2, i.e., dHv(x, y) = 1. This shows that (ii) holds. Suppose now that v ∈ NG(A), say vw ∈ E(G ◦H) for some w ∈ A. Since S is a hop independent set and dG◦H(w, z) = 2 for all z ∈ V (Hv), it follows that Sv = ∅, showing that (iii) holds. For the converse, suppose that S has the given form and satisfies (i), (ii), and (iii). Let a, b ∈ S, where a 6= b, and let v, w ∈ V (G) such that a ∈ V (v +Hv) and b ∈ V (w +Hw). Consider the following cases: Case 1. v 6= w. Suppose a = v and b = w. Then a, b ∈ A. Since A is a hop independent set of G, dG◦H(a, b) = dG(a, b) 6= 2. Suppose now that a = v and b 6= w (or a 6= v and b = w). Then a ∈ A and b ∈ Sw. By (iii), w /∈ NG(A). Hence, wv /∈ E(G) and dG◦H(a, b) 6= 2. If if a 6= v and b 6= w, then a ∈ Sv and b ∈ Sw. Clearly, dG◦H(a, b) 6= 2. Case 2. v = w. If one of a and b is v, say a = v, then b ∈ Sv and dG◦H(a, b) = 1 6= 2. If a 6= v and b 6= w, then a, b ∈ Sv. By (ii), Sv is a clique in Hv and so dG◦H(a, b) = 1 6= 2. Therefore, S is a hop independent set of G ◦H. Lemma 1. Let G be a non-trivial connected graph and let A be a hop independent set of G. Then |A| ≤ |NG(A)|. J. Hassan, S. Canoy, Jr., A. Aradais / Eur. J. Pure Appl. Math, 15 (2) (2022), 467-477 473 Proof. Note that A = (A \NG(A)) ∪ (A ∩NG(A)). Since G is a non-trivial connected graph, NG(a) 6= ∅ for each a ∈ A \ NG(A). Now let a, b ∈ A \ NG(A) with a 6= b. Suppose NG(a) ∩ NG(b) 6= ∅, say x ∈ NG(a) ∩ NG(b). Since A is a hop independent set of G, dG(a, b) 6= 2. Hence, ab ∈ E(G), implying that a ∈ A ∩ NG(A). This contradicts the assumption that a ∈ A \NG(A). Therefore, NG(a) ∩NG(b) = ∅ for any two distinct vertices a and b in A\NG(A). For each a ∈ A\NG(A), choose va ∈ (V (G)\A)∩NG(a) (such vertex va exists because G is non-trivial and connected) and let D = {va : a ∈ A\NG(A)}. Then D ⊆ NG(A) and |D| = |A \NG(A)|. Thus, |A| = |A ∩NG(A)|+ |A \NG(A)| = |A ∩NG(A)|+ |D| ≤ |NG(A)|. This proves the assertion. Corollary 3. Let G be a non-trivial connected graph and let H be any graph. Then αh(G ◦H) = |V (G)|ω(H). Proof. Let Sv be an ω-set of Hv for each v ∈ V (G). Then S = ∪v∈V (G)Sv is a hop independent set of G◦H by Theorem 5. This implies that αh(G◦H) ≥ |S| = |V (G)|ω(H). Next, let S∗ be a αh-set of G ◦H. Then S∗ = A ∪ (∪v∈V (G)Rv) and satisfies (i), (ii), and (iii) of Theorem 5. Hence, by Theorem 5 and Lemma 1, we have αh(G ◦H) = |S∗| = |A|+ ∑ v∈V (G) |Rv| = |A|+ ∑ u∈NG(A) |Ru|+ ∑ v/∈NG(A) |Rv| = |A|+ ∑ v/∈NG(A) |Rv| ≤ |A|+ (|V (G)| − |NG(A)|)ω(H) = |A| − |NG(A)|ω(H) + |V (G)|ω(H) ≤ |A| − |NG(A)|+ |V (G)|ω(H) ≤ |V (G)|ω(H). This proves the desired equality. 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) and (v, a)(u, b) ∈ E(G[H]) if and only if either uv ∈ E(G) or u = v and ab ∈ E(H). Note that any non-empty set C ⊆ V (G)× V (H) can be written 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 non-trivial connected graphs. Then C = ⋃ x∈S [{x} × Tx], J. Hassan, S. Canoy, Jr., A. Aradais / Eur. J. Pure Appl. Math, 15 (2) (2022), 467-477 474 where S ⊆ V (G) and Tx ⊆ V (H) for each x ∈ S, is a hop independent set of G[H] if and only if the following conditions hold. (i) S is a hop independent set of G. (ii) Tx is a clique in H for each x ∈ S. Proof. Suppose C = ⋃ x∈S [{x} × Tx] is a hop independent set of G[H]. Let v, w ∈ S with v 6= w and let a ∈ Tv and b ∈ Tw. Since (v, a), (w, b) ∈ C and C is a hop independent set of G[H], it follows that dG[H]((v, a), (w, b)) = dG(v, w) 6= 2. This implies that S is a hop independent set of G, showing that (i) holds. Next, let x ∈ S. If |Tx| = 1, then Tx is a clique in H. Suppose |Tx| ≥ 2 and let p, q ∈ Tx, where p 6= q. Then (x, p) and (x, q) are distinct elements of C. Since C is a hop independent set of G[H], dG[H]((x, p), (x, q)) 6= 2. Now, since G is non-trivial and connected, it follows that dH(p, q) = 1. Thus, Tx is a clique in H, showing that (ii) holds. For the converse, suppose that C = ⋃ x∈S [{x} × Tx] and satisfies (i) and (ii). Let (y, a), (z, b) ∈ C with (y, a) 6= (z, b). Consider the following cases: Case 1. y = z. Then a, b ∈ Ty. From condition (ii), Tx is a clique in H and so dH(a, b) = 1. Hence, dG[H]((y, a), (y, b)) = 1 6= 2. Case 2. y 6= z. Since y, z ∈ S and S is a hop independent set of G, dG(y, z) 6= 2. It follows that dG[H]((y, a), (z, b)) = dG(y, z) 6= 2. Accordingly, C is a hop independent set of G[H]. Corollary 4. Let G and H be non-trivial connected graphs. Then αh(G[H]) = αh(G)ω(H). Proof. Let S be a αh-set of G and let D be a clique in H with |D| = ω(H). For each x ∈ S, set Tx = D. Then C = ⋃ x∈S [{x}×Tx] = S×D is a hop independent set of G[H] by Theorem 6. Hence, αh(G[H]) ≥ |C| = αh(G)ω(H). Next, let C0 = ⋃ x∈S0 [{x} × Rx] be a αh-set of G[H]. By Theorem 6, S0 is a hop independent set of G and Tx is a clique in H. Hence, αh(G[H]) = |C0| = ∑ x∈S0 |Tx| ≤ |S0|ω(H) ≤ αh(G)ω(H). This establishes the desired equality. J. Hassan, S. Canoy, Jr., A. Aradais / Eur. J. Pure Appl. Math, 15 (2) (2022), 467-477 475 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) and (v, a)(u, b) ∈ E(G[H]) if and only if either a = b and uv ∈ E(G) or u = v and ab ∈ E(H). Theorem 7. Let G and H be non-trivial connected graphs. Then C = ⋃ x∈S [{x} × Tx], where S ⊆ V (G) and Tx ⊆ V (H) for each x ∈ S, is a hop independent set of G�H if and only if the following conditions hold. (i) Tx is a hop independent set of H for each x ∈ S; (ii) For each x ∈ S ∩NG(S) and for each y ∈ S ∩NG(x), it holds that dH(p, q) 6= 1 for all p ∈ Tx and q ∈ Ty; and (iii) For each v ∈ S ∩N2 G(S) and for each w ∈ S ∩N2 G(v), it holds that dH(a, b) ≥ 1 for all a ∈ Tv and b ∈ Tw. Proof. Suppose C = ⋃ x∈S [{x} × Tx] is a hop independent set of G�H. Let x ∈ S and let a, b ∈ Tx with a 6= b. Since (x, a) and (x, b) are distinct elements of C and C is a hop independent set of G�H, dH(a, b) = dG�H((x, a), (x, b)) 6= 2, showing that (i) holds, i.e., Tx is a hop independent set of H. Next, let x ∈ S∩NG(S) and let y ∈ S∩NG(x). Take any p ∈ Tx and q ∈ Ty. Suppose dH(p, q) = 1. Clearly, (x, p) and (y, q) are distinct elements of C and since p 6= q, dG�H((x, p), (y, q)) 6= 1. Since [(x, p), (x, q), (y, q)] is an (x, p)-(y, q) geodetic in G�H, dG�H((x, p), (y, q)) = 2, contrary to the fact that C is a hop independent set of G�H. Thus, dH(p, q) 6= 1, showing that (ii) holds. Finally, let v ∈ S ∩N2 G(S) and let w ∈ S ∩N2 G(v). Choose any a ∈ Tv and b ∈ Tw. Then (v, a), (w, b) ∈ C. Again, since C is a hop independent set of G�H, dG�H((v, a), (w, b)) 6= 2. Since dG(v, w) = 2, a 6= b. Thus, dH(a, b) ≥ 1, showing that (iii) holds. For the converse, suppose that C satisfies conditions (i), (ii), and (iii). Let (x, p), (y, q) ∈ C such that (x, p) 6= (y, q). Consider the following cases: Case 1. x = y. Then p 6= q and p, q ∈ Tx. From condition (i), it follows that dG�H((x, p), (y, q)) = dH(p, q) 6= 2. Case 2. x 6= y. Clearly, if dG(x, y) ≥ 3, then dG�H((x, p), (y, q)) 6= 2. Next, suppose that dG(x, y) = 1. Then by condition (ii), dH(p, q) 6= 1. If dH(p, q) = 0, then dG�H((x, p), (y, q)) = 1 6= 2. If dH(p, q) ≥ 2, then dG�H((x, p), (y, q)) = 1+ dH(p, q) ≥ 3. Suppose now that dG(x, y) = 2. Then by (iii), dH(p, q) ≥ 1. Hence, dG�H((x, p), (y, q)) = dG(x, y) + dH(p, q) ≥ 3. Therefore, C is a hop independent set of G�H. A set S is a 3-hop set of a connected graph G if dG(v, w) = 3 for every pair of distinct vertices v, w ∈ S. The maximum cardinality of a 3-hop set of G is denoted by α3 h(G). REFERENCES 476 Corollary 5. Let G and H be non-trivial connected graphs. Then αh(G�H) ≥ max{α3 h(G)αh(H), α3 h(H)αh(G)}. Proof. Let S be a 3-hop set of G with |S| = α3 h(G) and let D be an αh-set of H. Set Tx = D for each x ∈ S. Then C = ⋃ x∈S [{x} × Tx] = S × D is a hop independent set of G�H by Theorem 7. Hence, αh(G�H) ≥ |C| = |S||D| = α3 h(G)αh(H). Since G�H and H�G are isomorphic, the assertion holds. The bound given in Corollary 5 is attainable. To see this, consider P4�K4. Note that αh(K4) = 4 and α3 h(P4) = 2. One can easily verify that αh(P4�K4) = 8 = α3 h(P4)αh(K4). The bound, however, may not be attained. Consider, for example, P4�P4. It can also be verified that αh(P4�K4) = 6 > 4 = α3 h(P4)αh(P4). 4. Conclusion The concept of hop independent set in a graph, though maybe considered informally previously, has been introduced formally and investigated initially in this study. It is shown that the hop independence number of a graph is an upper bound of the hop domination number of the graph and that the absolute difference of the independence number and hop independence number can be made arbitrarily large. Just like the independence number, the hop independence number of a graph may be used to give bounds on some graph-theoretic parameters. In this paper the concept has been investigated for the join, corona, lexicographic and Cartesian products of graphs. Finding better bounds on the hop independence number of the Cartesian product of some graphs is recommended. Also, this newly defined parameter can be studied further for other types of graphs. Acknowledgements The authors would like to thank the referees for the invaluable assistance they gave us through their comments and suggestions which led to the improvement of the paper. Also, the authors would like to thank the Department of Science and Technology - Accelerated Science and Technology Human Resource Development Program (DOST-ASTHRDP)- Philippines, and MSU-Iligan Institute of Technology for funding this research. References [1] S. Arriola and Jr. S. Canoy. (1, 2)∗-domination in graphs. Advances and Applications in Discrete Mathematics., 18(2):179–190, 2017. [2] 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. REFERENCES 477 [3] M. Henning and N. Rad. On 2-step and hop dominating sets in graphs. Graphs and Combinatorics., 33(4):913–927, 2017. [4] C. Natarajan and S. Ayyaswamy. Hop domination in graphs ii. Versita, 23(2):187–199, 2015. [5] Jr. S. 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. [6] Jr. S. Canoy and G. Malacas. Differentiating-dominating sets in graphs under binary operations. Tamkang J. Math., 46(1):51–60, 2015. [7] Jr. S. Canoy, R. Mollejon, and J. G. Canoy. Hop dominating sets in graphs under binary operations. Eur. J. Pure Appl. Math., 12(4):1455–1463, 2019. [8] Jr. S. Canoy and G. Salasalan. Locating-hop domination in graphs. Kyungpook Math- ematical Journal, 62:193–204, 2022. [9] G. Salasalan and Jr. S. Canoy. Global hop domination numbers of graphs. Eur. J. Pure Appl. Math., 14(1):112–125, 2021.