EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS Vol. 15, No. 2, 2022, 342-353 ISSN 1307-5543 – ejpam.com Published by New York Business Global A Variant of Hop Domination in Graphs Sergio R. Canoy, Jr.1, Gemma P. Salasalan2,∗ 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 Department of Arts and Sciences, Institute of Arts and Sciences, Davao del Sur State College, Matti, Digos, Davao del Sur, Philippines Abstract. Let G be a connected graph with vertex and edge sets V (G) and E(G), respectively. 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. A set S ⊆ V (G) is a super hop dominating set if ehpnG(v, V (G) \ S) ̸= ∅ for each v ∈ V (G) \ S, where ehpnG(v, V (G) \ S) is the set containing all the external hop private neighbors of v with respect to V (G) \ S. The minimum cardinality of a super hop dominating set of G, denoted by γs h(G), is called the super hop domination number of G. In this paper, we investigate the concept and study it for graphs resulting from some binary operations. Specifically, we characterize the super hop dominating sets in the join, and lexicographic products of graphs, and determine bounds of the super hop domination number of each of these graphs. 2020 Mathematics Subject Classifications: 05C69 Key Words and Phrases: hop domination, super hop domination, complement-super domina- tion, join, lexicographic product 1. Introduction Super domination in a graph was first introduced and studied by Lemanska et al. in [8]. This concept uses the concept of external private neighbor of a vertex in some subset of the vertex set of a graph. Dettlaff et al. in [3] determined the super domination number of lexicographic products of graphs. Also, Dettlaff in [2] determined some values and bounds for the super domination number of some Cartesian products of graphs. Paraico and Canoy in [13] characterized the super dominating sets in the lexicographic and the Cartesian products of graphs and obtained bounds for the super domination numbers of these graphs. Recently, Natarajan and Ayyaswamy [11] introduced and studied the concept of hop domination in a graph. Ayyaswamy et al. in [1] also investigated the concept and obtained ∗Corresponding author. DOI: https://doi.org/10.29020/nybg.ejpam.v15i2.4352 Email addresses: sergio.canoy@g.msuiit.edu.ph (S. Canoy, Jr.) gemma.salasalan@dssc.edu.ph (G. Salasalan) https://www.ejpam.com 342 © 2022 EJPAM All rights reserved. S. Canoy, Jr., G. Salasalan / Eur. J. Pure Appl. Math, 15 (2) (2022), 342-353 343 bounds of the hop domination number of some graphs. The concept and some of its variations are also studied in [5], [6], [7], [10], [9], [12], and [14]. Motivated by these previous studies and, in particular, [3], [8], and [13], we introduce herein the concept of super hop domination and investigate it for some graphs and graphs resulting from the join, and lexicographic product of two graphs. 2. Terminology and Notation Let G = (V (G), E(G)) be a connected graph and let v ∈ V (G). The open neighborhood of v is the set NG(v) = {z ∈ V (G) : vz ∈ E(G)} and its closed neighborhood is NG[v] = NG(v) ∪ {v}. The open hop neighborhood of v is the set N2 G(v) = {u ∈ V (G) : dG(u, v) = 2}, where dG(u, v) denotes the distance between vertices u and v in G. The closed hop neighborhood of v is N2 G[v] = N2 G(v) ∪ {v}. The open hop neighborhood of A ⊆ V (G) is the set N2 G(A) = ∪v∈AN 2 G(v) and its closed hop neighborhood is N2 G[A] = A ∪N2 G(A). A set S ⊆ V (G) is a dominating set (hop dominating set) of a graph G if for each v ∈ V (G) \ S, there exists w ∈ S such that dG(v, w) = 1 (resp. dG(v, w) = 2). The smallest cardinality of a dominating (resp. hop dominating) set of G, denoted by γ(G) (resp. γh(G)), is called the domination number (resp. hop domination number) of G. Let S be a subset of V (G) and let v ∈ S. A vertex w ∈ V (G) \ S is an external private neighbor (external hop private neighbor) of v with respect to S if NG(w)∩S = {v} (resp. N2 G(w)∩S = {v}). The set containing all the external private neighbors (resp. hop private) neighbors of v with respect to S is denoted by epnG(v, S) (resp. ehpnG(v, S)). A set S ⊆ V (G) is called a super dominating set (resp. super hop dominating set) if epnG(v, V (G)\S) ̸= ∅ (resp. ehpnG(v, V (G)\S) ̸= ∅) for each v ∈ V (G)\S. The smallest cardinality of a super dominating (resp. super hop dominating) set of G, denoted by γs(G) (resp. γsh(G)), is called the super domination number (resp. super hop domination number) of G. Any super dominating (resp. super hop dominating) set of G with cardinality γs(G) (resp. γsh(G)) is called a γs-set (resp. γ s h-set) of G. A subset D of V (G) is a complement-super dominating set of G (super dominating set of G) if for each v ∈ V (G) \ D, there exists w ∈ D \ NG(v) = D ∩ NG(v) such that [V (G) \ NG(w)] ∩ [V (G) \ D] = NG(w) ∩ [V (G) \ D] = {v}. The smallest cardi- nality of a complement-super dominating set of G, denoted by γcs(G) = γs(G), is called the complement-super domination number of G (super domination number of G). Any complement-super dominating set of G with cardinality equal to γcs(G) is called a γcs-set. 3. Results Remark 1. γsh(Kn) = n for all n ≥ 1. Proposition 1. Let G be a graph of order n ≥ 1. Then max{γh(G), ⌈n2 ⌉} ≤ γsh(G) ≤ n. Proof. Since every super hop dominating set is hop dominating, it follows that γh(G) ≤ γsh(G). Now let S be a γsh-set of G. Then, by definition of super hop dominating set, S. Canoy, Jr., G. Salasalan / Eur. J. Pure Appl. Math, 15 (2) (2022), 342-353 344 |S| ≥ |V (G) \ S|. This implies that γsh(G) = |S| ≥ ⌈n2 ⌉. Moreover, since V (G) is a super hop dominating set, we have ⌈n2 ⌉ ≤ γsh(G) ≤ n. Therefore, the assertion holds. Theorem 1. Let G be a graph of order n ≥ 1. Then γsh(G) = n if and only if each component C of G is a complete graph. Proof. Suppose that γsh(G) = n. Suppose further that there exists a component C of G such that C is not a complete graph. Then there exist x, y ∈ V (C) such that dC(x, y) = dG(x, y) = 2. This implies that S = V (G) \ {x} is a super hop dominating set of G. Hence, γsh(G) ≤ |S| = n − 1, contrary to the assumption that γsh(G) = n. Thus, each component of G is a complete graph. For the converse, suppose that each component of G is a complete graph. Let S be a γsh-set of G and suppose that S ̸= V (G). Let v ∈ V (G) \ S and let C be the component of G with v ∈ V (C). Let w ∈ ehpnG(v, V (G) \ S). Then w ∈ V (C) and dG(v, w) = 2, contrary to the assumption that C is a complete graph. Thus, S = V (G), showing that γsh(G) = n. The next results are consequences of Theorem 1. Corollary 1. Let G be a connected graph of order n. Then γsh(G) = n if and only if G = Kn. Corollary 2. Let G be a connected non-complete graph of order n. Then γsh(G) ≤ n− 1. Corollary 3. If G is the complete graph of order n, then γsh(G) + γsh(G) = 2n and γsh(G).γsh(G) = n2. Theorem 2. Let G be a connected non-complete graph of oder n. Then (i) n ≤ γsh(G) + γsh(G) ≤ 2n− 1 and (ii) n2 4 ≤ γsh(G).γsh(G) ≤ n2 − n. Proof. By Corollary 2, γsh(G) ≤ n − 1. Also, by Proposition 1, γsh(G) ≤ n. These imply that γsh(G) + γsh(G) ≤ (n− 1) + n = 2n− 1 and γsh(G).γsh(G) ≤ (n− 1)n = n2 − n. The left inequalities follow from Proposition 1. Note that the upper bounds in Theorem 2 are tight. Indeed, if G = K1,n−1, then G = K1∪Kn−1. It is easy to show that γsh(G) = n−1. By Theorem 1, γsh(G) = n. Hence, γsh(G)+ γsh(G) = 2n− 1 and γsh(G).γsh(G) = n2−n. The lower bounds are also attainable. It can be verified that γsh(P4) + γsh(P 4) = 4 and γsh(P4).γ s h(P 4) = 16 4 = 4. The join of graphs G and H is the graph G+H with vertex set V (G+H) = V (G) ∪ V (H) and edge set E(G+H) = E(G) ∪ E(H) ∪ {uv : u ∈ V (G) and v ∈ V (H)}. Theorem 3. Let G and H be any two graphs. A subset S of V (G + H) is a super hop dominating set of G+H if and only if S = SG∪SH where SG and SH are complement-super dominating sets of G and H, respectively. S. Canoy, Jr., G. Salasalan / Eur. J. Pure Appl. Math, 15 (2) (2022), 342-353 345 Proof. Suppose that S is a super hop dominating set of G +H. Let SG = S ∩ V (G) and SH = S ∩ V (H). Let v ∈ V (G) \ SG. Since S is a super hop dominating set of G+H, there exists w ∈ ehpn(v, V (G+H) \ S). Since V (H) ⊆ NG+H(v), it follows that w ∈ SG \NG(v) and N2 G+H(w) ∩ (V (G+H) \ S) = [V (G) \NG(w)] ∩ [V (G) \ SG] = {v}. This shows that SG is a complement-super dominating set of G. Similarly, SH is a complement-super dominating set of H. For the converse, suppose that S = SG ∪ SH , where SG and SH are complement- super dominating sets of G and H, respectively. Let v ∈ V (G + H) \ S. If v ∈ V (G), then v ∈ V (G) \ SG. Since SG is a complement-super dominating set of G, there exists w ∈ SG\NG(v) such that [V (G)\NG(w)]∩[V (G)\SG] = N2 G+H(w)∩(V (G+H)\S) = {v}. This implies that w ∈ ehpn(v, V (G + H) \ S). Similarly, if v ∈ V (G) \ SH , then there exists z ∈ ehpn(v, V (G + H) \ S). This shows that S is a super hop dominating set of G+H. Theorem 4. Let G be a graph of order n. Then ⌈n2 ⌉ ≤ γcs(G) ≤ n. Moreover, (i) γcs(G) = n if and only if G = Kn; and (ii) for n ≥ 4 and even, we have γcs(G) = n 2 if and only if G has an (n2 − 1)-regular bipartite subgraph H with partite sets A and B such that V (G) = A ∪ B = V (H), |A| = |B| = n 2 and E(G) = E(⟨A⟩)∪E(⟨B⟩)∪E(H), where ⟨A⟩ is the graph induced by A. Proof. Let S be a complement-super dominating set of G. By definition, |S| ≥ |V (G)\ S| = n− |S|. Hence, |S| ≥ n 2 , showing that ⌈n2 ⌉ ≤ γcs(G) ≤ n. For (i), suppose that γcs(G) = n. Since γcs(G) = γs(G), it follows that G = Kn. Hence, G = Kn. The converse is clear. To show (ii), suppose first that γcs(G) = n 2 . Let S be an γcs-set of G. Then |S| = n 2 . Let v ∈ V (G) \ S. Then there exists xv ∈ S \NG(v) such that [V (G) \NG(xv)] ∩ (V (G) \ S) = {v}. Since |V (G) \ S| = n 2 and S is a complement-super dominating set of G, vy ∈ E(G) for all y ∈ S \ {xv}. Thus, NG(v) ∩ S = S \ {xv}. Let u, v ∈ V (G) \ S with u ̸= v. Since NG(xv) ∩ (V (G) \ S) = V (G) \ (S ∪ {v}), it follows that u ∈ NG(xv). Since u /∈ NG(xu), xu ̸= xv. Hence, S = {xv : v ∈ V (G) \ S}. Let A = S and B = V (G) \ S. Consider the bipartite graph H with partite sets A and B. Then |A| = |B| = n 2 . Since NG(v) ∩ S = S \ {xv} for each v ∈ B, it follows that degH(v) = n 2 − 1 for each v ∈ B. Also, since [V (G) \NG(xv)]∩ (V (G) \S) = {v} for each v ∈ B, degH(xv) = n 2 − 1 for each xv ∈ A. Thus, H is an (n2 −1)-regular graph. Moreover, E(G) = E(⟨A⟩)∪E(⟨B⟩)∪E(H). For the converse, suppose that G has the given property. Let v ∈ B = V (G) \ A. Then by assumption, degH(v) = n 2 − 1. This implies that there exists w ∈ A such [V (H) \ NH(w)] ∩ B = {v}. Since E(G) = E(⟨A⟩) ∪ E(⟨B⟩) ∪ E(H), it follows that S. Canoy, Jr., G. Salasalan / Eur. J. Pure Appl. Math, 15 (2) (2022), 342-353 346 [V (G) \NG(w)] ∩ B = [V (H) \NH(w)] ∩ B = {v}. This shows that A is a complement- super dominating set of G. Therefore n 2 ≤ γcs(G) ≤ |A| = n 2 , i.e., γcs(G) = n 2 . Theorem 5. Let G be a graph of order n. Then (i) γcs(G) = 1 if and only if G = K1 or G = K2. (ii) γcs(G) = 2 if and only if G ∈ {K2, P3,K2 ∪K1,K3, P4, C4,K2 ∪K2}. Proof. (i) Suppose γcs(G) = 1 and let S = {v} be a γcs-set of G. By Theorem 4, 1 ≤ n ≤ 2. If n = 1, then G = K1. Suppose n = 2 and let w ∈ V G) \ {v}. Since S is a complement-super dominating set of G, vw /∈ E(G). It follows that G = K2. The converse is clear. (ii) Suppose γcs(G) = 2. Then 2 ≤ n ≤ 4 by Theorem 4. Let S = {a, b} be a γcs-set of G. If n = 2, then G = K2 since γcs(K2) = 1. Suppose n = 3 and let c ∈ V (G)\S. We may assume that [V (G)\NG(a)]∩[V (G)\S] = {c}. If ab ∈ E(G), then G = P3 or G = K2∪K1. If ab /∈ E(G), then G = K3 or G = K2 ∪K1. Finally, let n = 4 and let V (G) = {a, b, c, d}. Since S is a γcs-set, we may assume that [V (G) \NG(a)] ∩ [V (G) \ S] = {c} and [V (G) \ NG(b)] ∩ [V (G) \ S] = {d}. Then ad, bc ∈ E(G). Suppose ab ∈ E(G). If cd ∈ E(G), then G = C4. If cd /∈ E(G), then G = P4. Next, suppose that ab /∈ E(G). If cd ∈ E(G), then G = P4. Otherwise, G = K2∪K2. Therefore, G ∈ {K2, P3,K2∪K1,K3, P4, C4,K2∪K2}. The converse is clear. Theorem 6. Let n be a positive integer. Then γcs(Pn) =  n if n = 1, 2 2 if n = 3 n− 2 if n ≥ 4. Proof. Let Pn = [v1, v2, · · · , vn]. Clearly, γcs(P1) = 1, γcs(P2) = 2, and γcs(P3) = 2. Suppose n ≥ 4. Since S0 = V (Pn) \ {v1, vn} is a complement-super dominating set of Pn, it follows that γcs(Pn) ≤ n − 2. Suppose γcs(Pn) < n − 2. Let S be a γcs-set of Pn and let v, w, and x be distinct elements of V (Pn) \ S. We may assume that v = vj , w = vr, and x = vs where 1 ≤ j < r < s ≤ n. Since S is a complement-super dominating set of Pn and w ∈ V (Pn) \S, there exists p ∈ S such that [V (Pn) \NPn(p)]∩ [V (Pn) \S] = {w}. This implies that pv, px ∈ E(Pn). Since j < s, it follows that p = vj+1 and s = j+2. This, however, would imply that r = j+1 (i.e., w = vr = p because j < r < s), a contradiction. Therefore, γcs(Pn) = n− 2. Theorem 7. Let n be a positive integer and n ≥ 3. Then γcs(Cn) = { 3 if n = 3, 6 n− 2 if n = 4, 5 and n ≥ 7. S. Canoy, Jr., G. Salasalan / Eur. J. Pure Appl. Math, 15 (2) (2022), 342-353 347 Proof. Let Cn = [v1, v2, · · · , vn, v1]. Now γcs(C3) = 3 by Theorem 4. Suppose 4 ≤ n ≤ 5. It can be verified easily that S0 = V (Cn) \ {v1, v2} is a γcs-set of Cn. Thus, γcs(Cn) = n− 2. Next, suppose that n = 6. Since S1 = V (C6) \ {v1, v3, v5} = {v2, v4, v6} is a complement-super dominating set of Cn, γcs(C6) = 3 by Theorem 4. Lastly, suppose that n ≥ 7. The set S∗ = V (Cn) \ {v1, v2} = {v3, v4, · · · , vn} is a complement-super dominating set of Cn. Consequently, γcs(Cn) ≤ n−2. Let S be a γcs-set of Cn and suppose |S| < n−2. Let a, b, and c be distinct elements of V (Cn)\S. We may assume that a = v1, b = vm, and c = vr where 1 < m < r ≤ n. Since S is a complement-super dominating set of Cn and c ∈ V (Cn)\S, there exists y ∈ S such that [V (Cn)\NCn(y)]∩ [V (Cn)\S] = {c}. This implies that ay, yb ∈ E(Cn). With the assumption that a = v1 and m < r, we find that y = v2 and b = v3. Applying the same argument to a ∈ V (Cn) \ S, we find that there exists z ∈ S such that [V (Cn) \NCn(z)]∩ [V (Cn) \S] = {a}. Hence, bz, zc ∈ E(Cn), implying that z = v4 and c = v5. Finally, for b ∈ V (Cn) \ S, there also exists q ∈ S such that [V (Cn) \NCn(q)] ∩ [V (Cn) \ S] = {b}. It follows that qv1, qv5 ∈ E(Cn). Since n ≥ 7, no such vertex q of Cn exists. Consequently, S is not a complement-super dominating set of Cn, a contradiction. Therefore, γcs(Cn) = n− 2. Theorem 8. Let G be a graph of order n ≥ 2. If S is a complement-super dominating set of G, then V (G) \ S contains at most a single isolated vertex of G. In particular, if G = Kn, then S = V (G)\{v} is a γcs-set of G for each v ∈ V (G), that is, γcs(G) = n−1. Proof. If S = V (G), then we are done. Suppose S ̸= V (G) and let v ∈ V (G) \ S. Then there exists w ∈ S such that [V (G) \ NG(w)] ∩ [V (G) \ S] = {v}. Hence, if v is an isolated vertex of G, then there can be no other isolated vertex in V (G) \ S. In other words, V (G) \ S contains at most a single isolated vertex of G. Suppose now that G = Kn and let v ∈ V (G). Then clearly, S = V (G) \ {v} is a complement-super dominating set of G. Since it is not possible for V (G) \ S to contain more than one isolated vertices, it follows that S is a γcs-set of G. Thus, γcs(G) = n−1. Theorem 9. Let G1, G2, · · · , Gn be the components of a graph G, where n ≥ 2. Then S ⊆ V (G) is a complement-super dominating set of G if and only if one of the following holds: (i) S = D ∪ [∪j ̸=kV (Gj)] for some k ≤ n and for some complement-super dominating set D of Gk. (ii) S = V (G) \ {v} for some isolated vertex v or S = [V (Gk) \ {v}] ∪ [∪j ̸=kV (Gj)] for some non-trivial component Gk and for some v ∈ V (Gk). (iii) S = [V (Gk)\{v}]∪[V (Gr)\{w}]∪[ ⋃ j ̸=k,r V (Gj)] for distinct non-trivial components Gk and Gr and for some v ∈ V (Gk) and w ∈ V (Gr). Proof. Suppose S is a complement-super dominating set of G. If S = V (G), then we may take D = V (G1) which is a complement-super dominating set of G1. Hence, S of type (i). Suppose S ̸= V (G). Let v ∈ V (G) \ S and let k ∈ {1, 2, · · · , n} such that v ∈ V (Gk). S. Canoy, Jr., G. Salasalan / Eur. J. Pure Appl. Math, 15 (2) (2022), 342-353 348 Since S is a complement-super dominating set of G, there exists z ∈ S such that [V (G) \ NG(z)] ∩ [V (G) \ S] = {v}. Suppose first that z ∈ V (Gk). Then clearly, ∪j ̸=kV (Gj) ⊆ S. Let D = S∩V (Gk). Then [V (Gk)\NGk (z)]∩[V (Gk)\D] = {v}. Thus, if D = V (Gk)\{v}, then D is a complement-super dominating set of Gk. Suppose D ̸= V (Gk) \ {v} and let x ∈ V (Gk)\(D∪{v}). Then there exists y ∈ S such that [V (G)\NG(y)]∩[V (G)\S] = {x}. Since x ̸= v, it follows that y ∈ D and [V (Gk) \ NGk (y)] ∩ [V (Gk) \D] = {x}. Thus, D is a complement-super dominating set of Gk, showing that (i) holds. Next, suppose that z ∈ V (Gr) for some r ≤ n with r ̸= k and let D∗ = S ∩ V (Gr). Note that if Gk ̸= ⟨v⟩, then [V (Gk)\{v}]∪ [∪j ̸=k,rV (Gj)] ⊆ S. Suppose first that D∗ = V (Gr). If Gk = ⟨v⟩, then S = V (G) \ {v}. Otherwise, S = [V (Gk) \ {v}] ∪ [∪j ̸=kV (Gj)]. Hence, S is of type (ii). Next, suppose that D∗ ̸= V (Gr). Let w ∈ V (Gr) \D∗. Then z ∈ NG(w). Let p ∈ S such that [V (G) \NG(p)] ∩ [V (G) \ S] = {w}. Since v ∈ [V (G) \ S] ∩ V (Gk))], p /∈ ∪j ̸=kV (Gj). Hence, p ∈ V (Gk) ∩ NGk (v). Moreover, |V (Gr) \ D∗| = 1, that is, D∗ = V (Gr) \ {w}. Consequently, S = [V (Gk)\{v}]∪ [V (Gr)\{w}]∪ [∪j ̸=r,kV (Gj)], showing that (iii) holds. For the converse, suppose first that S is of type (i), that is, S = D ∪ [∪j ̸=kV (Gj)] for some k ≤ n and for some complement-super dominating set D of Gk. Let v ∈ V (G) \ S. Then v ∈ V (Gk) \D. Since D is a complement-super dominating set of Gk, there exists z ∈ D such that [V (Gk) \NGk (z)] ∩ [V (Gk) \D] = {v}. It follows that [V (G) \NG(z)] ∩ [V (G) \ S] = {v}, showing that S is a complement-super dominating set of G. Clearly, if S is of type (ii), then S is a complement-super dominating set of G. Finally, suppose that S = [V (Gk) \ {v}] ∪ [V (Gr) \ {w}] ∪ [ ⋃ j ̸=k,r V (Gj)] for some k, r ≤ n, where v ∈ V (Gk), w ∈ V (Gr), and both [V (Gk) \ {v}] and [V (Gr) \ {w}] are non-empty sets. Pick p ∈ V (Gk) ∩NGk (v) and q ∈ V (Gr) ∩NGr(w). Then [V (G) \NG(p)] ∩ [V (G) \ S] = {w} and [V (G)\NG(q)]∩ [V (G)\S] = {v}, showing that S is a complement-super dominating set of G. Theorem 10. Let G1, G2, · · · , Gk, where k ≥ 2, be the components of a graph G of order n. Then each of the following statements holds. (i) γcs(G) = n−1 if and only if G = Kn or G has exactly a single non-trivial component Gs and |V (Gs)| − 1 ≤ γcs(Gs) ≤ |V (Gs)|. (ii) If G has at least two non-trivial components, then γcs(G) = min{n− 2, n− ηG}, where ηG = max{|V (Gj)| − γcs(Gj) : j = 1, 2, · · · , k}. Proof. (i) Suppose γcs(G) = n − 1. Suppose G ̸= Kn and assume that G has two non-trivial components, say Gm and Gr. Pick v ∈ V (Gm) and w ∈ V (Gr). Then S∗ = [V (Gk) \ {v}] ∪ [V (Gr) \ {w}] ∪ [∪j ̸=k,rV (Gj)] is a complement-super dominating set of G by Theorem 9(iii). Hence, γcs(G) ≤ |S∗| = n − 2, a contradiction. Since G ̸= Kn, G has exactly a single non-trivial component, say Gs. Let D be a γcs-set of Gs. Then S = D ∪ [∪j ̸=kV (Gj)] is a complement-super dominating set of G by Theorem 9(i). Since γcs(G) = n− 1 ≤ |S|, |V (Gs)| − 1 ≤ |D| = γcs(Gs) ≤ |V (Gs)|. S. Canoy, Jr., G. Salasalan / Eur. J. Pure Appl. Math, 15 (2) (2022), 342-353 349 For the converse, suppose first that G = Kn. Then γcs(G) = n−1 by Theorem 8. Next, suppose G has a single non-trivial component Gs and |V (Gs)| − 1 ≤ γcs(Gs) ≤ |V (Gs)|. Since V (G) \ {x} is a complement-super dominating set of G for each isolated vertex x, it follows that γcs(G) ≤ n − 1. Let S be a γcs-set of G. If γcs(Gs) = |V (Gs)|, then S of type (ii) by Theorem 9. Hence, γcs(G) = n − 1. If γcs(Gs) = |V (Gs)| − 1, then S = D∪ [∪j ̸=sV (Gj)] where D is γcs-set of Gs or S is of type (ii) by Theorem 9. In either case, γcs(G) = n− 1. (ii) Let Gm and Gr be non-trivial components and pick v ∈ V (Gm) and w ∈ V (Gr). Then S′ = [V (Gm)\{v}]∪[V (Gr)\{w}]∪[ ⋃ j ̸=k,r V (Gj)] is a complement-super dominating set of G by Theorem 9(iii). It follows that γcs(G) ≤ n− 2. Let S be a γcs-set of G. Since every complement-super dominating set of type (ii) (see Theorem 9) is of cardinality n−1, it follows that S is of type (i) or type (iii). If S is of type (iii), then γcs(G) = n−2. If S is of type (i), then there exists a (non-trivial component) Gs such that S = Ds ∪ [∪j ̸=sV (Gj)], where Ds is a γcs-set of Gs. In this case, γcs(G) = γcs(Gs) + ∑ j ̸=s |V (Gj)|. Hence, γcs(G) + |V (Gs)| − γcs(Gs) = n, that is, γcs(G) = n − [|V (Gs)| − γcs(Gs)]. Clearly, ηG = |V (Gs)| − γcs(Gs). Accordingly, γcs(G) = min{n− 2, n− ηG}. The next result is a consequence of Theorem 3, Theorem 4, and Theorem 10. Corollary 4. Let G and H be any two graphs of orders m and n, respectively. Then γsh(G+H) = γcs(G) + γcs(H). In particular, (i) γsh(G+H) = m+ n if G and H are complete; (ii) γsh(G+H) = m+ γcs(H) if G = Km; and (iii) γsh(G+H) = m+ n− 2 if G = Km and H = Kn for m,n ≥ 2. 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 11. Let G and H be any connected non-trivial graphs. Then C = ⋃ x∈S [{x}×Tx], where S ⊆ V (G) and Tx ⊆ V (H) for each x ∈ S, is a super hop dominating set of G[H] if and only if the following statements hold. (i) S = V (G). (ii) For each x ∈ S with |V (H) \ Tx| ≥ 2, the following conditions hold: (a) Tx is a complement-super dominating set of H, and S. Canoy, Jr., G. Salasalan / Eur. J. Pure Appl. Math, 15 (2) (2022), 342-353 350 (b) Ty = V (H) for all y ∈ N2 G(x). (iii) For each x ∈ V (G) with |V (H) \ Tx| = 1, at least one of the following conditions holds: (a) Tx is a complement-super dominating set of H and Ty = V (H) for all y ∈ N2 G(x). (b) There exist z ∈ N2 G(x) and t ∈ Tz such that Tw = V (H) for all w ∈ N2 G(z)\{x} and V (H) \ Tz ⊆ NH(t), where |V (H) \ Tz| ≤ 1. Proof. Suppose C = ∪x∈S({x} × Tx) is a super hop dominating set of G[H]. Suppose there exists x ∈ V (G) \ S and let a ∈ V (H). Since H is non-trivial, it follows that ehpnG[H] ((x, a), V (G[H]) \ C) = ∅, contrary to our assumption that C is a super hop dominating set. Thus, S = V (G), showing that (i) holds. Now let x ∈ S = V (G) with |V (H) \ Tx| ≥ 2 and let p ∈ V (H) \ Tx. Since C is a super hop dominating set of G[H], ehpnG[H]((x, p), V (G[H]) \ C) ̸= ∅. Let (y, q) ∈ ehpnG[H]((x, p), V (G[H]) \ C). By assumption, y /∈ N2 G(x). Hence, y = x and q ∈ Tx \ NH(p). Moreover, since (x, q) ∈ ehpnG[H]((x, p), V (G[H]) \ C), [V (H) \ NH(q)] ∩ [V (H) \ Tx] = {p} and Ty = V (H) for all y ∈ S ∩N2 G(x), showing that (a) and (b) of (ii) hold. Finally, let x ∈ S with |V (H)\Tx| = 1 and let p ∈ V (H)\Tx. Suppose that (a) of (iii) does not hold. Since C is a super hop dominating set of G[H] and (x, p) ∈ V (G[H])\C, let (z, t) ∈ ehpnG[H]((x, p), V (G[H]) \ C). This, together with the assumption, implies that z ∈ N2 G(x), t ∈ Tz, Tw = V (H) for all w ∈ N2 G(z) \ {x} and V (H) \ Tz ⊆ NH(t). Suppose |V (H)\Tz| > 1, say c, d ∈ V (H)\Tz where c ̸= d. Then ehpnG[H]((z, c), V (G[H])\C) = ∅, contrary to the assumption that C is a super hop dominating set of G[H]. Therefore, |V (H) \ Tz| ≤ 1, showing that (b) of (iii) holds. For the converse, suppose that C = ∪x∈S({x} × Tx) satisfies conditions (i), (ii), and (iii). Let (x, p) ∈ V (G[H])\C. Since S = V (G), p /∈ Tx. If |V (H)\Tx| ≥ 2, then by condi- tion (ii), there exists q ∈ ehpnH(p, V (H)\Tx). Clearly, (x, q) ∈ ehpnG[H]((x, p), V (G[H])\ C). Suppose that |V (H) \ Tx| = 1. Then by (iii), ehpnG[H]((x, p), V (G[H]) \ C) ̸= ∅. Accordingly, C is a super hop dominating set of G[H]. Let G be a graph. A set S ⊆ V (G) is a hop independent set of G if dG(x, y) ̸= 2 for any two vertices x, y ∈ S. The hop independence number of G, denoted by αh(G), is the largest cardinality of a hop independent set of G. Any hop independent set of G with cardinality αh(G) is called an αh-set of G. The concept has been introduced and studied in [4]. Corollary 5. Let G and H be non-trivial connected graphs of orders m and n, respectively. Then γsh(G[H]) ≤ (γcs(H)−n)αh(G)+mn. Moreover, if γcs(H) ≤ n−2, then γsh(G[H]) = (γcs(H)− n)αh(G) +mn. S. Canoy, Jr., G. Salasalan / Eur. J. Pure Appl. Math, 15 (2) (2022), 342-353 351 Proof. Let A be a αh-set of G and let D be a γcs-set of H. Set Tx = D for each x ∈ A and Tx = V (H) for each x ∈ V (G) \A. Then, by Theorem 11, C0 = ∪x∈V (G)({x}× Tx) = (A×D) ∪ [(V (G) \A)× V (H)] is a super hop dominating set of G[H]. Hence, γsh(G[H]) ≤ |C0| = |A||D|+ (m− |A|)n = αh(G)γcs(H) + [m− αh(G)]n = (γcs(H)− n)αh(G) +mn. Next, let C = ∪x∈V (G)({x} × Tx) be a γsh-set of G[H]. Let R = {v ∈ V (G) : |V (H) \ Tv| ≥ 2}. Since C is a super hop dominating set, R must be a hop independent set of G by Theorem 11(ii). Also, since C is a γsh-set of G[H], Tv is a γcs-set of H for each v ∈ R. Now let u ∈ V (G) \ R and suppose that |V (H) \ Tu| = 1. By Theorem 11(ii), dG(u,w) ̸= 2 for all w ∈ R (otherwise, Tu = V (H), a contradiction). Suppose that Tx = V (H) for all x ∈ N2 G(u). Replace Tu by a γcs-set T ′ u of H. Then the set C∗ = ∪x∈V (G)\{u}({x} × Tx) ∪ ({u} × T ′ u) is a super hop dominating set of G[H] by Theorem 11. Moreover, |C∗| < |C|, contrary to the assumption that C is a γsh-set of G[H]. Hence, Tx ̸= V (H) for some x ∈ N2 G(u). It follows from Theorem 11(iii) that there exists a z ∈ N2 G(u) and t ∈ Tz such that Tw = V (H) for all w ∈ N2 G(z) \ {u} and V (H)\Tz ⊆ NH(t), where |V (H)\Tz| ≤ 1. Replace Tu by T ′ u = V (H) and Tz by a γcs-set T ′ z of H. Then the set C1 = ∪x∈V (G)\{z,u}({x}×Tx)∪({u}×T ′ u)∪({z}×T ′ z) is a super hop dominating set of G[H] by Theorem 11. Clearly, |T ′ u| = |Tu|+ 1. If γcs(H) ≤ n− 3, then |T ′ z| < |Tz| − 1 and a straightforward computation shows that |C1| < |C|, a contradiction. Thus, Tu = V (H) for all u ∈ V (G) \ R. Since C is a γsh-set of G[H], it follows that R is a αh-set of G. This implies that γsh(G[H]) = |C| = (γcs(H) − n)αh(G) + mn. Suppose now that γcs(H) = n − 2. Suppose further that Tz = V (H). Then |T ′ z| < |Tz| − 1 and |C1| < |C|, a contradiction. Hence, |Tz| = n − 1. It follows that |T ′ z| = |Tz| − 1 and |C1| = |C|. This means that in the γsh-set C we may assume further that Tu = V (H) for each u ∈ V (G)\R. Again, as C is a γsh-set of G[H], R would be a αh-set of G, establishing the desired equality. We point out that the equality in Corollary 5 does not necessarily hold if γcs(H) = n−1, where n = |V (H)|. To see this, consider G = P4 and H = P3. Then αh(G) = 2 and γcs(H) = 2. It can be verified easily that γsh(G[H]) = 8 < 10 = (2 − 3)(2) + (4)(3) = [γcs(H)− 3]αh(G) + 12. Corollary 6. Let H be a connected graph and let m be a positive integer. Then γsh(Km[H]) = { γsh(H) , m = 1 m.γcs(H) , m ≥ 2. Proof. The result is clear if m = 1. Suppose m ≥ 2 and let let C = ∪x∈V (Km)({x} × Tx) be a γsh-set of Km[H]. Then each Tx is a complement-super dominating set of H REFERENCES 352 by Theorem 11. In particular, Tx is a γcs-set of H for all x ∈ V (Km). Accordingly, γsh(Km[H]) = |C| = m.γcs(H). Conclusion: Super hop domination, a variant of hop domination, has been intro- duced and studied for some graphs and graphs resulting from the join and lexicographic product of two graphs. In the case of the join of graphs, the concept of complement-super domination plays a vital role. Finding the complement-super domination number of a graph is the same as determining the super domination number of the complement of the graph. It is conjectured that the problem of finding a super hop dominating set is not easy, that is, NP-hard (NP-complete). It is recommended that some bounds on the super hop domination be determined and that the parameter be studied for other graphs. Acknowledgements The authors would like to thank the referees for their comments and suggestions which helped improve the paper. Also, they would like to extend their thankfulness to the De- partment of Science and Technology - Accelerated Science and Technology Human Re- source Development Program (DOST-ASTHRDP)-Philippines, and MSU-Iligan Institute of Technology 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] M. Dettlaff. A note on the super domination number of cartesian product of graphs. arXiv:1705.00928v1, 2017. [3] M. Dettlaff, M. Lemanska, J.A. Rodriguez, and R. Zuazua. On the super domination number of lexicographic product of graphs. arXiv:1703.06034v1, 2017. [4] J. Hassan, S. Canoy Jr., and A. Aradais. Hop independent sets in a graph. European Journal of Pure and Applied Mathematics, accepted, 2022. [5] M. Henning and N. Rad. On 2-step and hop dominating sets in graphs. Graphs and Combinatorics, 33(4):913–927, 2017. [6] S. Canoy Jr, R. Mollejon, and J. G. Canoy. Hop dominating sets in graphs under binary operations. Eur. J. Pure Appl. Math., 12(4):1455–1463, 2019. [7] S. Canoy Jr and G. Salasalan. Locating-hop domination in graphs. Kyungpook Math- ematical Journal, 62:193–204, 2022. REFERENCES 353 [8] M. Lemanska, V. Swaminathan, Y.B. Venkatakrishnan, and R. Zuazua. Super domi- nating sets in graphs. Proceedings of the National Academy of Sciences, India Section A: Physical Sciences, 85(3):353–357, 2015. [9] R. Mollejon and S. Canoy Jr. Hop dominating sets in graphs under binary operations. European Journal of Pure and Applied Mathematics, 12(4):1455–1463, 2019. [10] R. Mollejon and S. Canoy Jr. Double hop dominating sets in a graph. Discrete Math- ematics, Algorithms and Applications, https://doi.org/10.1142/S1793830921500579, 2021. [11] C. Natarajan and S. Ayyaswamy. Hop domination in graphs ii. Versita, 102(10):2393– 2401, 2017. [12] Y. Pabilona and H. Rara. Connected hop domination in graphs under some binary operations. Asian-European Journal of Mathematics, 11(5):1850075–1–18500075–11, 2018. [13] S. Paraico and S. Canoy Jr. Super dominating sets in some products of graphs. Far East Journal of Mathematical Sciences, 23(2):187–199, 2015. [14] G. Salasalan and S. Canoy Jr. Global hop domination numbers of graphs. Eur. J. Pure Appl. Math., 14(1):112–125, 2021.