EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS Vol. 16, No. 1, 2023, 192-206 ISSN 1307-5543 – ejpam.com Published by New York Business Global Transversal Hop Domination in Graphs Maria Andrea O. Bonsocan 1, Ferdinand P. Jamil 2 1 Department of Mathematics and Statistics, College of Science and Mathematics, Mindanao State University-Iligan Institute of Technology, 9200 Iligan City, Philippines 2 Department of Mathematics and Statistics, College of Science and Mathematics, Center of Graph Theory, Algebra, and Analysis-Premier Research Institute of Science and Mathematics, Mindanao State University-Iligan Institute of Technology, 9200 Iligan City, Philippines Abstract. LetG be a graph. A set S ⊆ V (G) is a hop dominating set ofG if for every v ∈ V (G)\S, there exists u ∈ S such that dG(u, v) = 2. The minimum cardinality γh(G) of a hop dominating set is the hop domination number of G. Any hop dominating set of G of cardinality γh(G) is a γh-set of G. A hop dominating set S of G which intersects every γh-set of G is a transversal hop dominating set. The minimum cardinality γ̂h(G) of a transversal hop dominating set in G is the transversal hop domination number of G. In this paper, we initiate the study of transversal hop domination. First, we characterize graphs G whose values for γ̂h(G) are either n or n − 1, and we determine the specific values of γ̂h(G) for some specific graphs. Next, we show that for every positive integers a and b with a ≥ 2 and b ≥ 3a, there exists a connected graph G on b vertices such that γ̂h(G) = a. We also show that for every positive integers a and b with 2 ≤ a ≤ b, there exists a connected graph G for which γh(G) = a and γ̂h(G) = b. Finally, we investigate the transversal hop dominating sets in the join and corona of two graphs, and determine their corresponding transversal hop domination numbers. 2020 Mathematics Subject Classifications: 05C69 Key Words and Phrases: Hop dominating set, transversal hop dominating set, transversal hop domination number 1. Introduction The concept of domination in graphs was first introduced by Ore [16] in 1958 and C. Berge [2] in 1962. Thereafter, domination as well as its numerous variations have become among the most extensively studied research areas in graph theory. Given a family C of sets, a transversal of C is a set containing at least one element from each member of C . Transversals in graphs have received high attention since the last 30 years. In 1991, T. Andreae et al. [21] studied the clique-transversal sets of line graphs. DOI: https://doi.org/10.29020/nybg.ejpam.v16i1.4610 Email addresses: mariaandrea.bonsocan@g.msuiit.edu.ph (M.A. Bonsocan), ferdinand.jamil@g.msuiit.edu.ph (F. Jamil) https://www.ejpam.com 192 © 2023 EJPAM All rights reserved. M.A. Bonsocan, F. Jamil / Eur. J. Pure Appl. Math, 16 (1) (2023), 192-206 193 In 1996, the vertex transversals that dominate is introduced in [5]. The independent transversal domination is being investigated in [6, 20, 22]. Recently, A. Alwardi et al.[18, 19] investigated the transversal domination in graphs. In this paper, we introduce and initiate the study of transversal hop domination. All graphs considered here are finite, simple and undirected. For basic graph termi- nologies, we refer the readers to [3]. For a graph G = (V (G), E(G)), V (G) and E(G) are its vertex set and edge set, respectively. For S ⊆ V (G), |S| refers to the cardinality of S. In particular, |V (G)| is the order of G. Given two graphs G and H with disjoint vertex sets, the union of G and H is the graph G∪H whose vertex set is V (G∪H) = V (G)∪V (H) and edge set E(G∪H) = E(G)∪E(H). The join of G and H is the graph G + H with vertex set V (G) ∪ V (H) and edge set E(G) ∪ E(H) ∪ {uv : u ∈ V (G), v ∈ V (H)}. The corona of G and H is the graph G ◦H obtained by taking one copy of G and |V (G)| copies of H, and then joining the ith vertex of G to every vertex in the ith copy of H. In G ◦ H, we denote by Hv that copy of H which is being joined to the vertex v of G. We also denote by Hv + v that subgraph ⟨{v} ∪ V (Hv)⟩ of G ◦H induced by {v} ∪ V (Hv). For a vertex v of G, the open neighborhood of v in G is the set NG(v) = {u ∈ V (G) : uv ∈ E(G)}, while the closed neighborhood of v in G is the set NG[v] = NG(v) ∪ {v}. Any vertex u ∈ NG(v) is called a neighbor of v. The degree of a vertex v of G, denoted by degG(v), is the number |NG(v)| of neighbors of v. The distance between two vertices u, v ∈ V (G) is the number of edges in a shortest path that joins vertex u to vertex v, and is denoted by dG(u, v). Such shortest u-v path is called u-v geodesic. We define diam(G) = max{dG(u, v) : u, v ∈ V (G)}. Any geodesic of length equal to diam(G) is called a diametral path. For S ⊆ V (G), NG(S) = ∪v∈SNG(v) and NG[S] = NG(S) ∪ S. If NG[S] = V (G) (resp. NG(S) = V (G)), then S is a dominating set (resp. total dominating set) of G. For total dominating sets, G necessarily has no isolated vertex. The smallest cardinality of a dominating (resp. total dominating) set S of G, denoted by γ(G) (resp. γt(G)) is called the domination number (resp. total domination number). A dominating (resp. total dominating) set S of G with |S| = γ(G) (resp. |S| = γt(G)) is called a γ-set (resp. γt-set) of G. The reader is referred to the following references, namely [4, 7–12, 14], for the history and a bit of the succeeding developments of the theory of domination in graphs. For two vertices u and v of G, v is a hop neighbor of vertex u if dG(u, v) = 2. The set NG(u, 2) = {v ∈ V (G) : dG(v, u) = 2} is called the open hop neighborhood of u. The closed hop neighborhood of u inG refers toNG[u, 2] = NG(u, 2)∪{u}. For S ⊆ V (G), the open hop neighborhood and closed hop neighborhood of S refer to the sets NG(S, 2) = ∪u∈SNG(u, 2) and NG[S, 2] = NG(S, 2) ∪ S, respectively. In case NG[S, 2] = V (G), then S is a hop dominating set (or HD-set) of G. Provided G has no isolated vertex, S is a total hop dominating set (or tHD-set) of G if NG(S, 2) = V (G). The minimum cardinality of a HD- set (resp. tHD-set) of G, denoted by γh(G) (resp. γth(G)), is called the hop domination number (resp. total hop domination number) of G. Any HD-set (resp. tHD-set) with cardinality γh(G) (resp. γth(G)) is called a γh-set (resp. γth-set). References [15] and [17] are excellent references for hop domination and total hop domination, respectively. M.A. Bonsocan, F. Jamil / Eur. J. Pure Appl. Math, 16 (1) (2023), 192-206 194 A set S ⊆ V (G) is a (1, 2)∗-dominating set of G (resp. (1, 2)∗-total dominating set) if it is both a dominating (resp. a total dominating) set and a hop dominating set of G. The smallest cardinality of a (1, 2)∗ -dominating (resp. (1, 2)∗-total dominating) set of G, denoted by γ∗1,2(G) (resp.γ∗t1,2(G)) is called the (1, 2)∗ -domination number (resp. (1, 2)∗- total domination number) of G. A (1, 2)∗ -dominating (resp. (1, 2)∗ -total dominating) set S with |S| = γ∗1,2(G) (resp. |S| = γ∗t1,2(G)) is called a γ∗1,2-set (resp. γ∗t1,2-set) of G. The concept of (1, 2)∗-domination (a variation of (1, 2)-domination) is introduced in [1]. A subset S of V (G) is a point-wise non-dominating set (or PND-set) of G if for each v ∈ V (G) \ S, there exists u ∈ S such that v /∈ NG(u). The smallest cardinality of a PND-set of G, denoted pnd(G), is called the point-wise non-domination number of G. Any point-wise non-dominating set S of G with |S| = pnd(G) is called a pnd-set of G. The concept of point-wise non-domination was introduced in [1]. A hop dominating set S of G which intersects every γh-set of G is called a transversal hop dominating set or (THD-set). In other words, a THD-set is a hop dominating set of G which is represented by every γh-set of G. The minimum cardinality of a THD-set of G is called the transversal hop domination number of G and is denoted by γ̂h(G). Any THD-set S of G with |S| = γ̂h(G) is called a γ̂h-set. 2. Preliminary Results Clearly, γh(G) ≤ γ̂h(G) ≤ n for all connected graphs G of order n. In particular, γ̂h(G) = 1 if and only if G = K1. Proposition 1. Let G be a connected graph of order n. Then (i) γ̂h(G) = n if and only if G is a complete graph. (ii) For n ≥ 3, γ̂h(G) = n−1 if and only if G is one of the graphs P4, C4 and K2+Kn−2. Proof. It is clear that if G = Kn, then γh(G) = γ̂h(G) = n. Conversely, suppose γ̂h(G) = n. The conclusion is clear if n = 1, 2. Assume n ≥ 3. Suppose G is not complete. Since G is connected, there exist u, v ∈ V (G) such that dG(u, v) = 2. Let S = V (G) \ {v}, and let T be a γ̂h-set of G. Clearly, S is an HD-set of G. If v /∈ T , then T ⊆ S. Suppose that v ∈ T . Since {v} is not a hop dominating set of G, there exists w ∈ T with w ̸= v. Thus, w ∈ S ∩ T . Since T is arbitrary, S is a THD-set of G. Consequently, γ̂h(G) ≤ |S| = n− 1, a contradiction. Thus, G is a complete graph. If G is one of the graphs P4, C4 and K2 + Kn−2 where n ≥ 3, then γ̂h(G) = n − 1. Conversely, assume that γ̂h(G) = n− 1. Suppose diam(G) ≥ 4. Then G has order n ≥ 5. Let u, v ∈ V (G) such that dG(u, v) = 4. Then {u, v} is not a γh-set of G. It follows that S = V (G) \ {u, v} is a THD-set of G. Thus, γ̂h(G) ≤ |S| = n− 2, a contradiction. Hence, diam(G) ≤ 3. Consider the following cases: Case 1: Suppose that diam(G) = 3. Then G has order n ≥ 4. Let P = [u,w, x, v] be a diametral path in G. Let y ∈ V (G) \ V (P ) that is adjacent to any of the vertices in P . If wy ∈ E(G), then S = V (G) \ {u, y} is a HD-set of G. Since {u, y} is not M.A. Bonsocan, F. Jamil / Eur. J. Pure Appl. Math, 16 (1) (2023), 192-206 195 a HD-set of G, S is a THD-set of G. Thus, γ̂h(G) ≤ |S| = n − 2, a contradiction. Similar contradiction is attained if xy ∈ E(G). Suppose that uy ∈ E(G). Necessarily, 2 ≤ dG(y, v) ≤ 3. Since {w, y} is not a HD-set of G, S = V (G) \ {w, y} is a THD-set of G. Thus, γ̂h(G) ≤ |S| = n − 2, a contradiction. A similar contradiction is attained if yv ∈ E(G). Therefore, G = P = P4. Case 2: Suppose that diam(G) = 2 and G ̸= C4. Then G has order n ≥ 3. Let u, v ∈ V (G) such that dG(u, v) = 2. First, we claim that ux, vx ∈ E(G) for all x ∈ V (G)\{u, v}. This is clear if n = 3 i.e., G = P3. Assume n ≥ 4. Let [u,w, v] be a geodesic in G, and let y ∈ V (G) \ {u,w, v}. Suppose that uy /∈ E(G). Then dG(u, y) = 2, and say [u, z, y] is a u-y geodesic in G. The desired contradiction is attained as we consider the following subcases: Subcase 2.1: Suppose that z = w. Observe that S = V (G) \ {v, y} is a HD-set of G. Since T = {v, y} does not hop-dominate w, T is not a HD-set of G. Thus, S is a THD-set of G. Consequently, γ̂h(G) ≤ |S| = n− 2, a contradiction. Subcase 2.2: Suppose that w ̸= z and wy ∈ E(G). Then S = V (G) \ {v, y} is a HD-set of G. Since T = {v, y} is not a HD-set of G, S is a THD-set of G. This means that γ̂h(G) ≤ |S| = n− 2, a contradiction. Subcase 2.3: Suppose that w ̸= z and dG(y, w) = 2. Let [y, x, w] be a y-w geodesic in G. If x = z, then S = V (G)\{u, y} is a THD-set of G as {u, y} does not hop-dominate z. If x ̸= z, then S = V (G) \ {w, y} is a THD-set of G as {w, y} does not hop-dominate x. Accordingly, γ̂h(G) ≤ |S| = n− 2, a contradiction. Therefore, ux ∈ E(G) for all x ∈ V (G) \ {u, v}. Similarly, vx ∈ E(G) for all x ∈ V (G) \ {u, v}. Next, we claim that H = ⟨V (G)\{u, v}⟩ is complete. Suppose not, and let x, y ∈ V (H) with dH(x, y) = 2. Let [x, z, y] be a geodesic in H. In particular, [u, x, v] is a geodesic in G by the above claim. Observe also that S = V (G) \ {u, y} is a HD-set of G. By the first claim, uz ∈ E(G). Thus, {u, y} does not hop-dominate z. This means that S is a THD-set of G. Consequently, γ̂h(G) ≤ |S| = n − 2, a contradiction. Therefore, H is complete. Accordingly, G = ⟨{u, v}⟩+H = K2 +Kn−2. Theorem 1. If G is a disconnected graph with components G1, G2, . . . , Gm then γ̂h(G) = min 1≤k≤m {γ̂h(Gk) + m∑ j=1,j ̸=k γh(Gj)}. In particular, γ̂h(Kn) = n. Proof. For each k ∈ {1, 2, . . . ,m}, let Dk and Sk be a γ̂h-set and a γh-set, respectively, of Gk. Then Dk ∪ ( ∪m j=1,j ̸=kSj ) is a THD-set of G for all k ∈ {1, 2, . . . ,m}. Thus, γ̂h(G) ≤ min1≤k≤m{γ̂h(Gk) + ∑m j=1,j ̸=k γh(Gj)}. M.A. Bonsocan, F. Jamil / Eur. J. Pure Appl. Math, 16 (1) (2023), 192-206 196 To get the other inequality, let S be any THD-set of G. Then Tk = S ∩ V (Gk) is a HD-set for all k ∈ {1, 2, . . . ,m}. We claim that Tk is a THD-set of Gk for at least one k ∈ {1, 2, . . . ,m}. Suppose not, and let, for each k ∈ {1, 2, . . . ,m}, Sk be a γh- set of Gk for which Tk ∩ Sk = ∅. Since ∪m k=1Sk is a γh-set of G, S ∩ (∪m k=1)Sk ̸= ∅. Since S = ∪m k=1Tk, this is impossible and our claim holds. Hence, |S| = ∑m k=1 |Tk| ≥ min1≤k≤m{γ̂h(Gk) + ∑m j=1,j ̸=k γh(Gj)}. Theorem 2. Let G be any nontrivial graph. Then 4 ≤ γ̂h(G) + γ̂h(G) ≤ 2n, and these bounds are sharp. Proof. Let G be any nontrivial graph. Then, we have 2 ≤ γ̂h(G) ≤ n. Similarly, 2 ≤ γ̂h(G) ≤ n. Therefore, 4 ≤ γ̂h(G) + γ̂h(G) ≤ 2n. To show sharpness of the bounds, consider G = K2 for the lower bound and G = Kn for the upper bound. 3. On some specific graphs Proposition 2. Let G = Km1,m2,...,mk be a complete multipartite graph such that 1 ≤ m1 ≤ m2 ≤ . . . ≤ mk, and k ≥ 2. Then γ̂h(G) = m1 + k − 1. In particular, for m,n ≥ 1, γ̂h(Km,n) = 1 +min{m,n}. Proof. Let U1, U2, . . . Uk be the partite sets ofG with |Ui| = mi for each i ∈ {1, 2, . . . , k}. Then γh(G) = k, and S ⊆ V (G) is a γh-set of G if and only if |S ∩ Ui| = 1 for each i ∈ {1, 2, . . . , k}. Thus, T ⊆ V (G) is a THD-set of G if and only if T = Ui ∪ ( ∪k j=1;j ̸=iSj ) for some i ∈ {1, 2, . . . , k} and ∅ ̸= Sj ⊆ Uj for all j ̸= i. Consequently, γ̂h(G) = m1+k−1. Proposition 3. For a path Pn on n vertices, γ̂h(Pn) =  2, if n = 3, 5 3, if n = 4 2r, if n = 6r 2r + 1, if n = 6r + 1 2r + 2, if n = 6r + s, s = 2, 3, 4, 5 Proof. Let Pn = [v1, v2, . . . , vn]. The case where n = 3, 4, 5 can easily be verified. Let n ≥ 6 and let r and s be integers for which n = 6r + s with 0 ≤ s ≤ 5. Let S = {v3, v4, v9, v10, . . . , v6r−3, v6r−2}. If s = 0, then S is the unique γ̂h-set of Pn. In this case, γ̂h(Pn) = γh(Pn) = 2r. If s = 1, then every γh-set contains the vertex v4. Thus, γ̂h(Pn) = γh(Pn) = 2r + 1. Suppose that s ∈ {2, 3, 4, 5}. Then T = S ∪ {vn−2, vn−1} is a γ̂h-set of Pn. Thus, γ̂h(Pn) = |T | = 2r + 2. M.A. Bonsocan, F. Jamil / Eur. J. Pure Appl. Math, 16 (1) (2023), 192-206 197 Proposition 4. For a cycle Cn of length n, γ̂h(Cn) =  3, if n = 4, 5 2r + 2, if n = 6r, 6r + 1 2r + 3, if n = 6r + s, s = 2, 3, 4, 5 Proof. Let Cn = [v1, v2, . . . , vn, v1]. The case where n = 4, 5 can easily be verified. Let n ≥ 6 and write n = 6r+ s where 0 ≤ s ≤ 5. Let S = {v3, v4, . . . , v6r−3, v6r−2}. Then S ∪ {vn−4, vn}, S∪{vn−2, vn}, S∪{vn−2, vn−1, vn}, S∪{vn−3, vn−1, vn}, S∪{vn−4, vn−3, vn−2} and S ∪ {vn−5, vn−3, vn−2} are γ̂h-sets of Cn provided s = 0, s = 1, s = 2, s = 3, s = 4 and s = 5, respectively. Since |S| = 2r, the result follows. Proposition 5. Let G = Km(a1, a2, · · · , am) be a multi-star graph. Then γ̂h(G) = m for m ≥ 2. Proof. Let V (Km) = {v1, v2, . . . , vm} and for each i = 1, 2, 3 . . . ,m, let vix i j (j = 1, 2, . . . , ai) be the pendant edges joined with vi (Figure 1 shows the particular G with m = 4). Then the γh-sets of G are of the form {vi, xij}. Hence G has a unique γ̂h-set, .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... ..................................................................................................................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ................................................................................................................................................................................................................. ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ..... ..................................................................................................................................... .... ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ............................................................................. ................................................................... ....... ........ ........ ........ ........ ........ ........ ........ ....................................................................................... .......... .......... .......... .......... .......... . ............................................................... ..................................................................................................................................................... ......... ........ ........ ........ ........ ........ ........ ...... ............................................................................ ................. ................ ................ ................ ........ ............................................................... v1 v2 v3v4 x11 x12 . . . x1a1 x21 x22 . . . x2a2 x31 x32. . . x3a3 x41 x42 . . . x4a4 Figure 1: Multi-star K4(a1, a2, a3, a4) namely, the V (Km). Thus, γ̂h(G) = m. Proposition 6. For the Petersen graph P , γ̂h(P ) = 6. Proof. Let V (P ) = {x1, x2, x3, x4, x5, y1, y2, y3, y4, y5} where x1, x2, x3, x4, x5 are the vertices of the outer cycle and y1, y2, y3, y4, y5 are the corresponding vertices of the inner cycle. Then the γh-sets of P are of the form {xi, yi} where xiyi ∈ E(P ), {xi, xj} where xixj ∈ E(P ), i ̸= j and {yi, yj} where yiyj ∈ E(P ), i ̸= j for all i, j = 1, 2, . . . , 5. Thus, S = {xi, xj , xk, yi, yj , yk} is a γ̂h-set of P where xi and xj are adjacent in P and the vertex xk /∈ NP (xi)∪NP (xj) and yk is adjacent to the vertex xk in P and yi, yj /∈ NP (xi)∪NP (xj). Therefore, γ̂h(P ) = |S| = 6. M.A. Bonsocan, F. Jamil / Eur. J. Pure Appl. Math, 16 (1) (2023), 192-206 198 Proposition 7. Let G be a firefly graph with t ≥ 1 pendant paths, s ≥ 1 triangles and n− 2s− 2t− 1 ≥ 1 pendant edges. Then, γ̂h(G) = 2. Proof. Let G be a firefly graph as shown in Figure 2, where a is the vertex common to the triangles [a, a2k−1, a2k, a] (k = 1, 2, . . . , s), pendant edges [a,wk] (k = 1, 2, . . . , n−2s− 2t− 1) and pendant paths [a, uk, vk] (k = 1, 2, . . . , t) in G. If t = 1, then the γh-sets of G are the sets {a, u1}, {u1, v1} and the sets of the form {a,wi} for i ≥ 1. Hence, {a, u1} is the unique γ̂h-set of G. Therefore, γ̂h(G) = 2. Assume t > 1. Then the γh-sets of G are of the form {a,wi} and {a, ui} for i ≥ 1. Since the vertex a is in every γh-set of G. Therefore, γ̂h(G) = 2. .................................... ........................................................................ .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... ......................................................................................................................................................... ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ .... .......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ........ ...................................................................................................................................................... ................... .................. .................. .................. .................. .................. .................. .................. ..... ......... ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ .... ..................................................................................................................................................................................................................................................................................................... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ..... .............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ... .................................................................................................................................................................................................................................................................................................................. ............................................................................ ............................................................................ ............................................................................ a w1w2w3 a1 a2 a3 a4 u1 v1 u2 v2 u3 v3 Figure 2: firefly graph F2,3,3 4. Realization Problems Theorem 3. Let a and b be two positive integers with a ≥ 2 and b ≥ 3a. Then there exists a connected graph G on b vertices such that γ̂h(G) = a. Proof. Write b = 3a+ r for some integer r ≥ 0. Consider the corona Ka ◦K2, and let x ∈ V (Ka). Obtain G from Ka ◦ K2 by joining to Kx 2 + x, the complete graph Kr (see G in Figure 3 where a = 4 and r = 3). Then G is a connected graph on b vertices. If ........................................................................ .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... ............ ........... ........... ........... ........... ........... .... ......................................... ...................... ....................................................................... ............................................................... ................................... .......... ......... ......... .......................................... ......................................... ...................... ............ ........... ........... ........... ........... ........... .... ............................................................................ ......... ........ ........ ........ ........ ........ ........ ........ ........ .............................................................................................................................. ........... ........... ........... ........... ........... ........... ........... ........... ........... ............................................................................ .... ........ ........ ........ ........ ........ ........ ........ ........ ........ ......... ........ ........ ........ ........ ........ ........ ........ ........ ... ............ ........... ........... ........... ...... ............................................................................................................... ...................................................................................................................................................................................................................... ........... ........... ........... ........... ........... ........... ........... ........... ........... .......................... ......................... ......................... ......................... ......................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ... ................................................... .......................... ......................... ......................... ......................... ......................... .............................................................................................................................................................................. ........... ........... ........... ...... .......................................................................................................................................................................................................... ............................................................................. ......................... ......................... ......................... ......................... x Figure 3: Graph G where a = 4, r = 3 and |V (G)| = 3a+ r = 15 a = 2, then γh(G) = a and V (Ka) is the unique γh-set of G. In this case, V (Ka) is also the unique γ̂h-set of G so that γ̂h(G) = a. If a ≥ 3, then except for the case of a = 3 M.A. Bonsocan, F. Jamil / Eur. J. Pure Appl. Math, 16 (1) (2023), 192-206 199 which also includes V (Ka) as a γh-set, the γh-sets of G are all sets of the form {u, y, v} for distinct vertices u, v ∈ V (Ka) and y ∈ V (Hu) ∪ V (Hv) and {p, q, z} where z ∈ V (Ka) and p, q ∈ V (Kz 2 ). Thus, V (Ka) is a γ̂h-set of G. Therefore, γ̂h(G) = a. Theorem 4. For any positive integers a and b with 2 ≤ a ≤ b, there exists a connected graph G for which γh(G) = a and γ̂h(G) = b. Proof. If a = b, then we consider the complete graph Ka. By Proposition 1, γh(Ka) = a = γ̂h(Kb). Suppose that a < b. Then b = a + n for some positive integer n. Consider the graph G as shown in Figure 4. G is obtained from the rectangular grid graph L(a, 3) by adding the edges wivi and yizi and the paths [wi, x k i , yi] for each i ∈ {1, 2, . . . , a} and k ∈ {1, 2, . . . , n}. For each i ∈ {1, 2, 3, . . . , a}, let Ui = {xi, x1i , x2i . . . , xni }. Then γh(G) = a and S is a γh-set of G if and only if |S ∩ Ui| = 1 for all i = 1, 2, 3, . . . , a and S \ ∪a i=1Ui = ∅. In particular, the set S∗ = {x1, x2, x3, . . . , xa−1, xa} is a γh-set of G. Put D = S∗ ∪ U1. For each γh-set S of G, S ∩D ̸= ∅. Clearly, D is a γ̂h-set of G. Therefore, γ̂h(G) = |D| = a+ n = b. .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... ........................................................................ .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... ........... .......... .......... .......... .......... .......... . ................. ................ ................ ................ ........ ................................. ................................ ................................ ........... ...................................................................................... ................................................................................................................. ........................................................................................................................................................ ........... .......... .......... .......... .......... .......... . ................. ................ ................ ................ ........ ................................. ................................ ................................ ........... ...................................................................................... ................................................................................................................. ........................................................................................................................................................ ........... .......... .......... .......... .......... .......... . ................. ................ ................ ................ ........ ................................. ................................ ................................ ........... ...................................................................................... ................................................................................................................. ........................................................................................................................................................ ........... .......... .......... .......... .......... .......... . ................. ................ ................ ................ ........ ................................. ................................ ................................ ........... ...................................................................................... ................................................................................................................. ........................................................................................................................................................ ........... .......... .......... .......... .......... .......... . ................. ................ ................ ................ ........ ................................. ................................ ................................ ........... ...................................................................................... ................................................................................................................. ........................................................................................................................................................ ........... .......... .......... .......... .......... .......... . ................. ................ ................ ................ ........ ................................. ................................ ................................ ........... ...................................................................................... ................................................................................................................. ........................................................................................................................................................ ........... .......... .......... .......... .......... .......... . ................. ................ ................ ................ ........ ................................. ................................ ................................ ........... ...................................................................................... ................................................................................................................. ........................................................................................................................................................ ......... ........ ........ ........ ........ ........ ........ ..... ......... ........ ........ ........ ........ ........ ........ ..... ......... ........ ........ ........ ........ ........ ........ ..... ......... ........ ........ ........ ........ ........ ........ ..... ......... ........ ........ ........ ........ ........ ........ ..... ......... ........ ........ ........ ........ ........ ........ ..... ......... ........ ........ ........ ........ ........ ........ ..... ......... ........ ........ ........ ........ ........ ........ ..... ......... ........ ........ ........ ........ ........ ........ ..... ......... ........ ........ ........ ........ ........ ........ ..... ......... ........ ........ ........ ........ ........ ........ ..... ......... ........ ........ ........ ........ ........ ........ ..... ......... ........ ........ ........ ........ ........ ........ ..... ......... ........ ........ ........ ........ ........ ........ ..... ......... ........ ........ ........ ........ ........ ........ ..... ......... ........ ........ ........ ........ ........ ........ ..... ......... ........ ........ ........ ........ ........ ........ ..... ......... ........ ........ ........ ........ ........ ........ ..... ......... ........ ........ ........ ........ ........ ........ ..... ......... ........ ........ ........ ........ ........ ........ ..... ......... ........ ........ ........ ........ ........ ........ ..... ......... ........ ........ ........ ........ ........ ........ ..... ......... ........ ........ ........ ........ ........ ........ ..... ......... ........ ........ ........ ........ ........ ........ ..... ......... ........ ........ ........ ........ ........ ........ ..... ......... ........ ........ ........ ........ ........ ........ ..... ......... ........ ........ ........ ........ ........ ........ ..... ......... ........ ........ ........ ........ ........ ........ ..... ..................................................................................................................................... ..................................................................................................................................... ..................................................................................................................................... ..................................................................................................................................... ............................................................................ ............................................................................ ..................................................................................................................................... ..................................................................................................................................... ..................................................................................................................................... ..................................................................................................................................... ..................................................................................................................................... ..................................................................................................................................... ..................................................................................................................................... ..................................................................................................................................... ..................................................................................................................................... ..................................................................................................................................... ..................................................................................................................................... x1 x2 x3 x4 x5 . . . xa−1 xa y1 y2 y3 y4 y5 ya−1 ya z1 z2 z3 z4 z5 za−1 za v1 v2 v3 v4 v5 va−1 va w1 w2 w3 w4 w5 wa−1 wa x1 1 x2 1 . . . xn 1 x1 2 x2 2 . . . xn 2 x1 3 x2 3 . . . xn 3 x1 4 x2 4 . . . xn 4 x1 5 x2 5 . . . xn 5 x1 5 x2 5 . . . xn 5 x1 a−1 x2 a−1 . . . xn a−1 x1 a x2 a . . . xn a Figure 4: Graph G with γh(G) = a and γ̂h(G) = b Corollary 1. For each positive integer n, there exists a connected graph G such that γ̂h(G)− γh(G) = n. That is, the difference γ̂h − γh can be made arbitrarily large. 5. In the join of graphs To attain a precise characterization of transversal hop dominating sets in the join of graphs, we give the following definition. A set S ⊆ V (G) is a transversal point-wise non-dominating set (or TRPND-set) of G if S is a PND-set of G that intersects every pnd-set of G. The minimum cardinality of a TRPND-set of G, denoted trpnd(G), is the transversal point-wise non-domination number of G. Any transversal point-wise non- dominating set of G of cardinality trpnd(G) is referred to as a trpnd-set. For complete graphs, complete bipartite graphs, paths and cycles, we have trpnd(Kn) = n for all n ≥ 1; M.A. Bonsocan, F. Jamil / Eur. J. Pure Appl. Math, 16 (1) (2023), 192-206 200 trpnd(Km,n) = 1 +min{m,n} for all m,n not both equal to 1; trpnd(Pn) = { n− 1, if n = 3, 4 n− 2, if n ≥ 5; and trpnd(Cn) =  n− 1, if n = 4, n− 3, if n = 6, n− 2, if n = 5 and n ≥ 7. The following theorem is due to Canoy et al. [13] from which we draw the succeeding lemma. Theorem 5. [13] Let G and H be any two graphs. A set S ⊆ V (G+H) is hop dominating set of G +H if and only if S = SG ∪ SH , where SG and SH are PND-sets of G and H, respectively. Lemma 1. Let G and H be any two graphs. Then S is a γh-set of G+H if and only if S = SG ∪ SH , where SG ⊆ V (G) and SH ⊆ V (H) are pnd-sets of G and H, respectively. Theorem 6. Let G and H be any two graphs. Then S ⊆ V (G + H) is a THD-set of G +H if and only if S = SG ∪ SH where SG ⊆ V (G) and SH ⊆ V (H) for which one of the following holds: (i) SG is a TRPND-set of G and SH is a PND-set of H. (ii) SH is a TRPND-set of H and SG is a PND-set of G. Proof. Suppose that S is a THD-set of G+H. Put SG = S∩V (G) and SH = S∩V (H). Since S = SG ∪ SH is a hop dominating set of G +H, SG ̸= ∅ and SH ̸= ∅. Moreover, by Theorem 5, SG and SH are PND-sets of G and H, respectively. Suppose that SG and SH are, respectively, not TRPND-sets of G and H. There exist pnd-sets A and B of G and H, respectively, for which A ∩ SG = ∅ and B ∩ SH = ∅. By Lemma 1, A ∪ B is a pnd-set of G+H. Being a TRPND-set, S ∩ (A ∪B) ̸= ∅, which is impossible. Thus, the conclusion follows. Conversely, suppose S = SG ∪ SH where SG and SH are as described in (i). Let T = TG∪TH be a γh-set of G+H. Write TG = T ∩V (G) and TH = T ∩V (H). By Lemma 1, TG is a pnd-set of G. Thus, SG ∩ TG ̸= ∅. This means that S ∩ T ̸= ∅. Therefore, S is a THD-set of G +H. Similarly, if (ii) holds for SG and SH , then S is a THD-set of G+H. Corollary 2. Let G and H be any two graphs. Then γ̂h(G+H) = min{trpnd(G) + pnd(H), trpnd(H) + pnd(G)}. M.A. Bonsocan, F. Jamil / Eur. J. Pure Appl. Math, 16 (1) (2023), 192-206 201 6. In the corona of graphs (i) If H has no isolated vertex, then γ̂h(K2 ◦H) = 2. (ii) If H has k ≥ 1 isolated vertices, then γ̂h(K2 ◦H) = k + 2. Proposition 8. Let G be a connected graph of order n ≥ 3, and let H be any graph. Then γ̂h(G ◦H) ≤ n, and equality is attained if G = Kn. Proof. It is easy to verify that V (G) is a hop dominating set of G ◦ H. Let S be a γh-set of G ◦H. Suppose that S ∩V (G) = ∅. Then |S ∩V (Hv)| ≥ 1, say uv ∈ S ∩V (Hv), for each v ∈ V (G). Let [z, v, w] be a path in G. Define S∗ = (S \ {uz, uw}) ∪ {v}. To show that S∗ is a hop dominating set of G ◦H, it is enough to consider only the vertices in V (G) ∩ (NG(z) ∪NG(w)). Let a ∈ V (G) ∩ NG(z) with a ̸= v. If av ∈ E(G), then dG◦H(a, uv) = 2. On the other hand, if av /∈ E(G), then dG◦H(a, v) = 2. Thus, S∗ hop dominates V (G)∩NG(z). Similarly, S∗ hop dominates V (G)∩NG(w). This means that S∗ is a hop dominating set of G◦H with |S∗| < |S|, a contradiction. Therefore, S∩V (G) ̸= ∅ for all γh-sets S of G◦H so that V (G) is a THD-set of G◦H. Consequently, γ̂h(G◦H) ≤ n. Now, consider G = Kn. If H has an isolated vertex, then S is a γh-set of G ◦H if and only if S = {u, v} where v ∈ V (G) and u is an isolated vertex of Hv. In this case, V (G) is a γ̂h-set of G ◦H. Suppose that H has no isolated vertices. Then S is a γh-set of G ◦H if and only if one of the following holds for S: (i) S = V (G) (whenever n = 3); (ii) S = V (Hv + v) (whenever H = K2); (iii) S = {v, u, w} where v ∈ V (G) and u and w belong to distinct components of Hv (whenever H has at least 2 components); (iv) S = {v, u, w} where v ∈ V (G) and both u and w belong the same component of Hv such that for each z ∈ V (Hv) \ {u,w} we have uz /∈ E(Hv) or wz /∈ E(Hv); (v) S = {v, u, w} where u, v ∈ V (G) and w ∈ V (Hv) ∪ V (Hu). Therefore, V (G) is a γ̂h-set so that γ̂h(G ◦H) = n. The inequality in Proposition 8 can be strict. If G = K1,4 and H = K2, then γ̂h(G ◦ H) = 2 < n. Proposition 9. [1] Let G be a graph. Then 1 ≤ pnd(G) ≤ |V (G)|. Moreover, (i) pnd(G) = |V (G)| if and only if G is a complete graph; (ii) pnd(G) = 1 if and only if G has an isolated vertex; and M.A. Bonsocan, F. Jamil / Eur. J. Pure Appl. Math, 16 (1) (2023), 192-206 202 (iii) pnd(G) = 2 if and only if G has no isolated vertex and there exist distinct vertices a and b of G such that NG(a) ∩NG(b) = ∅. Theorem 7. [13] Let G and H be any two graphs. A set C ⊆ V (G◦H) is a hop dominating set of G ◦H if and only if C = A ∪ (∪v∈V (G)∩NG(A)Sv) ∪ (∪w∈V (G)\NG(A)Ew), where (i) A ⊆ V (G) such that for each w ∈ V (G) \A, there exists x ∈ A with dG(w, x) = 2 or there exists y ∈ V (G) ∩NG(w) with V (Hy) ∩ C ̸= ∅, (ii) Sv ⊆ V (Hv) for each v ∈ V (G) ∩NG(A), and (iii) Ew ⊆ V (Hw) is a point-wise non-dominating set of Hw for each w ∈ V (G)\NG(A). Lemma 2. Let G be a connected K3-free graph and H be a nontrivial connected graph, and let S ⊆ V (G ◦ H). Then S is a γh-set of G ◦ H if and only if S ⊆ V (G) and is a γ∗t1,2-set of G. Proof. Let S ⊆ V (G ◦ H) be a γh-set of G ◦ H. First, we claim that S ⊆ V (G). Assume, to the contrary, that Sv = S ∩ V (Hv) ̸= ∅ for some v ∈ V (G). Suppose that S ∩ NG(v) = ∅. By Theorem 7, Sv is a PND-set of Hv. By Proposition 9, |Sv| ≥ 2. Choose w ∈ NG(v), and define S∗ = (S \Sv)∪ {w}. Let x ∈ V (G ◦H) \S∗. If x ∈ V (Hy) for y ̸= v and z ∈ S is such that dG◦H(x, z) = 2, then z ∈ S∗. If x ∈ V (Hv), then dG◦H(w, x) = 2. Suppose that x ∈ V (G). Then x ∈ V (G) \ S and x ̸= w. There exists z ∈ S such that dG◦H(x, z) = 2. If z ∈ Sv, then dG◦H(x,w) = 2 since G is K3-free. If z /∈ Sv, then z ∈ S\Sv so that z ∈ S∗. This shows that S∗ is a hop dominating set of G◦H. Since |S∗| < |S|, this is a contradiction. Suppose, S ∩ NG(v) ̸= ∅. Let w ∈ S ∩ NG(v). Define T = S \Sv. Following similar argument, T is a hop dominating set of G ◦H. Since |T | < |S|, this is a contradiction. Therefore, S ⊆ V (G). Now, let x ∈ V (G). Pick u ∈ V (Hx). Then u /∈ S and there exists v ∈ S for which dG◦H(u, v) = 2. Necessarily, dG(x, v) = 1. Therefore, S is a (1, 2)∗-total dominating set of G. Hence, |S| ≥ γ∗t1,2(G). Suppose that A ⊆ V (G) is a γ∗t1,2-set of G. Then A is a hop dominating set of G ◦H so that |S| ≤ |A| = γ∗t1,2(G). Therefore, S is a γ∗t1,2-set of G. Conversely, suppose that S ⊆ V (G) is a γ∗t1,2-set of G. Then S is a hop dominating set of G. Let v ∈ V (G) and x ∈ V (Hv). Since S is a total dominating set of G, uv ∈ E(G) for some u ∈ S. Then dG◦H(x, u) = 2. Since x and v are arbitrary, S hop dominates V (Hv) for all v ∈ V (G). Thus S is a hop dominating set of G ◦H. Let S∗ be a γh-set of G. By the above result, S∗ ⊆ V (G) and is a γ∗t1,2-set of G. Therefore, |S| = |S∗| and S is a γh-set of G ◦H. Corollary 3. For all connected K3-free graphs G and nontrivial connected graphs H, γh(G ◦H) = γ∗t1,2(G). M.A. Bonsocan, F. Jamil / Eur. J. Pure Appl. Math, 16 (1) (2023), 192-206 203 ............... .............. .............. .............. .............. .............. ........ .................................... ............................................................................................. .................................... .................................................................................................................................................................. ........................................................................ .................................... .................................... .................................... .................................... .................................... .................................... ................................................................ ......... ......... ......... ......... ........ ............................................... ................................................................ ......... ......... ......... ......... ........ ............................................... ................................................................ ......... ......... ......... ......... ........ ............................................... • • • Figure 5: The corona K3 ◦K2 It is worth noting that the necessity part of Lemma 2 need not be true if G contains a K3. Consider, for example, the corona K3 ◦K2 as shown in Figure 5. Observe that the blackened vertices constitute a γh-set of K3 ◦K2. For what follows, we give the following definition. A subset S ⊆ V (G) is said to be a transversal (1, 2)∗-total dominating set of G if S is a (1, 2)∗-total dominating set of G which intersects every γ∗t1,2-set of G. The minimum cardinality of a transversal (1, 2)∗-total dominating set, denoted γ̂∗t1,2(G), is the transversal (1, 2)∗-total domination number of G. Any transversal (1, 2)∗-total dominating set of G of cardinality γ̂∗t1,2(G) is referred to as a γ̂∗t1,2-set. Theorem 8. If G is a connected K3-free graph of order n ≥ 2, then γ̂h(G ◦H) = γ̂∗t1,2(G) for all nontrivial connected graphs H. Proof. This is clear if n = 2. Suppose that n ≥ 3. First, let S ⊆ V (G) be a γ̂∗1,2-set of G. Following the sufficiency proof of Lemma 2, S is a hop dominating set of G ◦H. By Lemma 2, S is a THD-set of G ◦H. Consequently, γ̂h(G ◦H) ≤ |S| = γ̂∗t1,2(G). Now, let S ⊆ V (G◦H) be a γ̂h-set of G◦H. Let A = S∩V (G) and Sv = S∩V (Hv) for each v ∈ V (G). By Theorem 7 and Proposition 9, Sv is a PND-set of Hv, hence |Sv| ≥ 2, for all v ∈ V (G) \NG(A). For each v ∈ V (G) \NG(A), choose uv ∈ NG(v). Define C = A ∪ {v, uv : v ∈ V (G) \NG(A)}. Clearly, |C| ≤ |S|. Claim 1: C is a hop dominating set of G. Let x ∈ V (G) \ C. Since S is a hop dominating set of G ◦ H and x /∈ S, there exists y ∈ S for which dG◦H(x, y) = 2. If y ∈ A, then y ∈ C. Suppose that y /∈ A and A ∩ NG(x, 2) = ∅. Then there exists v ∈ V (G) such that xv ∈ E(G) and y ∈ V (Hv). Since G is K3-free, v ∈ V (G) \NG(A). Thus, there exists uv ∈ NG(v) such that v, uv ∈ C. Since G is K3-free, dG(x, uv) = 2. This shows that C is a hop dominating set of G. Claim 2: C is a total dominating set of G. Let v ∈ V (G). If v ∈ NG(A), then there exists u ∈ C such that uv ∈ E(G). Suppose that v /∈ NG(A). Then there exists uv ∈ NG(v) such that v, uv ∈ C. In this case, uv is the desired vertex in C for which vuv ∈ E(G). Accordingly, C is a total dominating set of G. REFERENCES 204 Claim 1 and Claim 2 all show that C is a (1, 2)∗-total dominating set of G. Let T ⊆ V (G) be a γ∗t1,2-set of G. By Corollary 3, T is a γh-set of G ◦H. Thus, S ∩ T ̸= ∅. This means that A ∩ T ̸= ∅. Therefore, C ∩ T ̸= ∅ and C is a transversal (1, 2)∗-total dominating set of G. Consequently, γ̂∗t1,2(G) ≤ |C| ≤ |S| = γ̂h(G ◦H). Example 1. Let H be a nontrivial connected graph. 1. For a path Pn on n vertices, γ̂h(Pn ◦H) = γ̂∗t1,2(Pn) =  2, if n = 2, 3; 2r, if n = 4r; 2r + 1, if n = 4r + 1; 2r + 2, if n = 4r + s, s = 2, 3. 2. For a cycle Cn of order n ≥ 4, γ̂h(Cn ◦H) = γ̂∗t1,2(Cn) = { 2r + 1, if n = 4r, 4r + 1 2r + 2, if n = 4r + 2, 4r + 3 3. For the complete bipartite graph Km,n with m,n ≥ 2, γ̂h(Km,n ◦H) = γ̂∗t1,2(Km,n) = 1 +min{m,n}. Acknowledgements The authors would like to thank the Department of Science and Technology - Acceler- ated Science and Technology Human Resource Development Program (DOST-ASTHRDP)- Philippines, MSU-Iligan Institute of Technology. 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] C. Berge. Theory of graphs and its Applications. Methuen, London, 1962. [3] F. Buckley and F. Harary. Distance in Graphs. Addison-Wesley, Redwood City, CA, 1990. [4] E. Cockayne and S. Hedetniemi. Towards a theory of domination in graphs. Networks, 7(3):247–261, 1977. REFERENCES 205 [5] N. Alon M.R. Fellows and D.R. Hare. Vertex transversals that dominate. Journal of Graph Theory, 21(1):21–31, 1996. [6] I.S. Hamid. Independent transversal domination in graphs. Discussiones Mathemat- icae Graph Theory, 32:5–7, 2012. [7] JW.J. Desormeaux T.W. Haynes and M.A. Henning. An extremal problem for total domination stable graphs upon edge removal. Discrete Appl. Math, 159:1048–1052, 2011. [8] T.W. Haynes S.T. Hedetniemi and P.J. Slater. Fundamentals of Domination in Graphs. Marcel Dekker, Inc., New York, 1990. [9] M. Henning and A. Yeo. Total domination in graphs. Springer, 2013. [10] F.P. Jamil and H.N. Maglanque. Cost effective domination in the join, corona and composition of graphs. European Journal of Pure and Applied Mathematics, 12(3):978–998, 2019. [11] F.P. Jamil and R.P. Malalay. On disjunctive domination in graphs. Quaestiones Mathematicae, 43(2):149–168, 2020. [12] R.G. Eballe R. Aldema E.M. Paluga R.F. Rulete F.P. Jamil. Global defensive alliances in the join, corona and composition of graphs. Ars Combinatoria, 107:225–245, 2012. [13] J.G.Canoy 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. [14] P. Dankelmann D. Day D. Erwin S. Mukwembi and H. Swart. Domination with exponential decay. Discrete Math, 309(19):5877 – 5883, 2009. [15] C. Natarajan and S.K. Ayyaswamy. Hop domination in graphs-II. Versita, 23(2):187– 199, 2015. [16] O. Ore. Theory of Graphs, volume 38. 1962. [17] Y. Pabilona and H. Rara. Total hop dominating sets in the join, corona, and lexico- graphic product of graphs. ournal of Algebra and Applied Mathematics, 2017. [18] A. Alwardi N. Abhi R. Puttaswamy. Transversal domination in graphs. Gulf Journal of Mathematics, 6:41–49, 2018. [19] A. Alwardi N. Abhi R. Puttaswamy. Transversal Total Domination in Graphs. preprint at https://www.researchgate.net/publication/325063470, 2018. [20] H.A. Ahangar V. Samodivkin and I. Yero. Independent transversal dominating sets in graphs: complexity and structural properties. Filomat, 30(2):293–303, 2016. REFERENCES 206 [21] T. Andreae M. Schughart and Z. Tuza. Clique-transversal sets of line graphs and complements of line graphs. Discrete Mathematics, 88(1):11–20, 1991. [22] D.S. Sevilleno and F.P. Jamil. On independent transversal dominating sets in graphs. European Journal of Pure and Applied Mathematics, 14(1):140–163, 2021.