EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS Vol. 17, No. 2, 2024, 852-859 ISSN 1307-5543 – ejpam.com Published by New York Business Global Formulas and Properties of 2-Hop Domination in Some Graphs Javier A. Hassan1,∗, Anabel E. Gomorez2, Ladznar S. Laja1, Eman C. Ahmad2 1Mathematics and Statistics Department, College of Arts and Sciences, MSU Tawi-Tawi College of Technology and Oceanography, Bongao, Tawi-Tawi, Philippines 2Department of Mathematics and Statistics, College of Science and Mathematics, Western Mindanao State University, Zamboanga City, Philippines Abstract. In this paper, 2-hop domination parameter is introduced and investigated on some special graphs and on the join of two graphs. Characterizations of 2-hop dominating sets in some special graphs are formulated to derive bounds or formulas of the parameter of these graphs. Moreover, new variant of pointwise non-domination is introduced to characterize 2-hop dominating sets in the join of two graphs. This characterization is used to calculate the exact value of 2-hop domination number of the join of two graphs. 2020 Mathematics Subject Classifications: 05C69 Key Words and Phrases: Hop dominating, 2-hop dominating set, 2-hop domination number 1. Introduction Hop domination is the variant of the standard domination and was introduced by Natarajan et al. in [12]. Hop domination has applications in various fields such as net- work design, communication networks, and facility location problems. Researchers con- tinue to explore various aspects of hop domination, including its computational complexity, structural properties, and applications in real-world networks. As graph theory and its applications continue to evolve, hop domination remains an active area of research, con- tributing to our understanding of network dynamics and optimization. Researchers in the field had further investigated this concept, and its variants. They have obtained some significant results that contributed a lot to the hop domination theory (see [1–11]). In this paper, new variant of hop domination called 2-hop domination is introduced and studied on some special graphs and on the join of two graphs. The researchers believe that this parameter and its results would contribute positively to the field of graph theory and would help other researchers in the field for more research directions in the future. DOI: https://doi.org/10.29020/nybg.ejpam.v17i2.5065 Email address: javierhassan@msutawi-tawi.edu.ph (J. Hassan), anabel.gamorez@wmsu.edu.ph (A. Gamorez), ladznarlaja@msutawi-tawi.edu.ph (L. Laja), ahmad.eman@wmsu.edu.ph (E. Ahmad) https://www.ejpam.com 852 © 2024 EJPAM All rights reserved. J. Hassan, A. Gomorez, L. Laja, E. Ahmad / Eur. J. Pure Appl. Math, 17 (2) (2024), 852-859 853 2. Terminology and Notation Let G = (V (G), E(G)) be a simple and undirected graph. The distance dG(a, b) in G of two vertices a, b is the length of a shortest a-b path in G. Two vertices x, y of G are adjacent or neighbors, if dG(x, y) = 1. The open neighbor- hood of x in G is the set NG(x) = {y ∈ V (G) : dG(x, y) = 1}. The closed neighborhood of x in G is the set NG[x] = NG(x) ∪ {x}. If X ⊆ V (G), the open neighborhood of X in G is the set NG(X) = ⋃ x∈X NG(x). The closed neighborhood of X in G is the set NG[X] = NG(X) ∪X. A vertex a in G is a hop neighbor of a vertex b in G if dG(a, b) = 2. The set N2 G(a) = {b ∈ V (G) : dG(a, b) = 2} is called the open hop neighborhood of a. The closed hop neighborhood of a in G is given by N2 G[a] = N2 G(a) ∪ {a}. The open hop neighborhood of S ⊆ V (G) is the set N2 G(S) = ⋃ a∈S N2 G(a). The closed hop neighborhood of S in G is the set N2 G[S] = N2 G(S)∪S. A subset S of V (G) is a hop dominating of G if for every a ∈ V (G)\S, there exists b ∈ S such that dG(a, b) = 2. The minimum cardinality among all hop dominating sets of G, denoted by γh(G), is called the hop domination number of G. Any hop dominating set with cardinality equal to γh(G) is called a γh-set of G. A subset C of V (G) is a pointwise non-dominating set if for every v ∈ V (G)\C, there exists u ∈ C such that v /∈ NG(u). The minimum cardinality of a pointwise non- dominating set in G, denoted by pnd(G), is called a pointwise non-domination number of G. Let G and H be any two graphs. The join of 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)}. 3. Results We begin this section by introducing the concept of 2-hop domination in a graph. Definition 1. Let G be a simple and undirected graph. A subset P of a vertex-set V (G) of G is called a 2-hop dominating if for every x ∈ V (G)\P , x has at least two hop neighbors in P . The 2-hop domination number of G, denoted by γ2h(G), is the minimum cardinality of a 2-hop dominating set of G. To further understand the aforementioned concept, consider the following example: Example 1. Consider the graph G below. J. Hassan, A. Gomorez, L. Laja, E. Ahmad / Eur. J. Pure Appl. Math, 17 (2) (2024), 852-859 854 a b c d e f g h G : Figure 1: Graph G with γ2h(G) = 5 Let P = {b, c, d, e, h}. Then V (G)\P = {a, f, g}. Observe that vertex a has two hop neighbors c and d in P , f has three hop neighbors b, c and h in P , and g has two neighbors d and e in P . Thus, P is a 2-hop dominating set of G. Moreover, it can be verified that γ2h(G) = 5. Remark 1. Let G be a graph. Then (i) a 2-hop dominating set P of G is always a hop dominating; and (ii) G admits a 2-hop domination. Theorem 1. Let G be a graph. Then (i) γh(G) ≤ γ2h(G), and this bound is tight; (ii) 1 ≤ γ2h(G) ≤ |V (G)|; and (iii) if G has |V (G)| ≥ 2, then γ2h(G) ≥ 2. Proof. (i) Let G be a graph and let P be a minimum 2-hop dominating set of G. Then γ2h(G) = |P |. Since every 2-hop dominating is a hop dominating, it follows that γh(G) ≤ |P | = γ2h(G). For tightness, consider Kn. Then γ2h(Kn) = n = γh(G). (ii) Since γh(G) ≥ 1 for any graph G, by(i), γ2h(G) ≥ 1. Now, Since every 2-hop dominating set P is always a subset of V (G), it follows that γ2h(G) ≤ |V (G)|. Therefore, 1 ≤ γ2h(G) ≤ |V (G)|. (iii) Suppose that γ2h(G) = 1. Then P = {a} ⊆ V (G) is minimum 2-hop dom- inating set of G for some a ∈ V (G). Since every 2-hop dominating is a hop domi- nating, N2 G[a] = V (G). Assume that there is b ∈ V (G)\P such that b ∈ N2 G[a]. Let x ∈ NG(a) ∩NG(b). Then x /∈ N2 G[a], a contradiction. Therefore, N2 G[a] = {a}, and so G is trivial. Consequently, |V (G)| = 1, a contradiction. Theorem 2. Let G be a graph. Then γ2h(G) = 2 if and only if G = K2 or G = K2. Proof. Suppose that γ2h(G) = 2, say P = {a, b} is a minimum 2-hop dominating set of G. Then N2 G[P ] = V (G) since every 2-hop dominating set P is a hop domi- nating. Assume that G is connected. If dG(a, b) = 2, then there exists y ∈ V (G)\P J. Hassan, A. Gomorez, L. Laja, E. Ahmad / Eur. J. Pure Appl. Math, 17 (2) (2024), 852-859 855 such that y ∈ NG(a) ∩ NG(b). However, y /∈ N2 G[P ], a contradiction. Similarly, when dG(a, b) = 3, 4, . . . , n− 1, where n is the order of G. Thus, dG(a, b) = 1, and so G = K2. Now, assume that G is disconnected. Let G1, . . . , Gk, k ≥ 2, be conponents of G. Since γ2h(G) = 2, it follows that k = 2. That is, there are only 2 components of G. If G1 is non-trivial, then γ2h(G1) ≥ 2 by Theorem 1 (iii). Since G has two components, it follows that γ2h(G) ≥ 3, a contradiction. Similarly, when G2 is non-trivial. Therefore, both G1 and G2 are trivial, and so G = K2. Conversely, suppose that G = K2. Then γh(G) = 2. Since γ2h(G) ≥ γh(G), it follows that γ2h(G) ≥ 2. Since |V (G)| = 2, γ2h(G) = 2 by Theorem 1(ii). Similarly, if G = K2, then γ2h(G) = 2. Theorem 3. Let G be a graph. Then (i) γ2h(G) = |V (G)| if and only if |N2 G[x]| ≤ 2 for every x ∈ V (G); and (ii) If γh(G) = |V (G)|, then γ2h(G) = |V (G)|. However, the converse is not true. Proof. (i) Suppose that γ2h(G) = |V (G)|. Then V (G) is the minimum 2-hop dominat- ing set of G, that is, N2 G[V (G)] = V (G). Assume that |N2 G[x]| ≥ 3 for some x ∈ V (G). Then there exist u, v ∈ V (G) such that u, v ∈ N2 G(x). Let P = V (G)\{x}. Then P is a 2-hop dominating set of G. Thus, γ2h(G) ≤ |V (G)| − 1, a contradiction. Therefore, |N2 G[x]| ≤ 2 for all x ∈ V (G). Conversely, suppose that |N2 G[x]| ≤ 2 for all x ∈ V (G). IfN2 G[x] = {x} for all x ∈ V (G), then we are done. Assume that |N2 G[x]| = 2 for all x ∈ V (G). Then there exists a unique y ∈ V (G) such that y ∈ N2 G(x). Let P be a 2-hop dominating set of G. Since P is a hop dominating, either x or y is in P . Assume that x ∈ P . Assume further that y /∈ P . Since P is a 2-hop dominating, there exists w ∈ P such that dG(w, y) = 2. It follows that w, x ∈ N2 G(y). Thus |N2 G[y]| ≥ 3, a contradiction. Therefore, y ∈ P . Similarly, when y ∈ P , then x ∈ P . Since x is arbitrary, it follows that V (G) is the minimum 2-hop dominating set of G. Consequently, γ2h(G) = |V (G)|. (ii) Suppose that γh(G) = |V (G)|. Then by Theorem 1, γ2h(G) = |V (G)|. To see that the converse is not true, conisder P4. Then γ2h(P4) = 4 by (i). However, γh(P4) = 2. The following definition will be used to characterize 2-hop dominating sets in the join of two graphs. Definition 2. Let G be a graph. A subset N of a vertex-set V (G) of G is called a 2-pointwise non-dominating if for every x ∈ V (G)\N , there exist at least two distinct vertices a, b ∈ N such that x /∈ NG(a) and x /∈ NG(b). The minimum cardinality of a 2-pointwise non-dominating set of G is the 2-pointwise non-domination number of G, and is denoted by pnd2(G). Remark 2. Let G be a graph. Then J. Hassan, A. Gomorez, L. Laja, E. Ahmad / Eur. J. Pure Appl. Math, 17 (2) (2024), 852-859 856 (i) every 2-pointwise non-dominating set is a pointwise non-dominating; (ii) pnd(G) ≤ pnd2(G); (iii) pnd2(Kn) = n for all positive integer n ≥ 1; (iv) pnd2(Kn) = { 1 , n = 1 2 , n ≥ 2; and (v) 1 ≤ pnd2(G) ≤ |V (G)|. Proposition 1. Let n be a positive integer. Then (i) pnd2(Pn) = { n , 1 ≤ n ≤ 3 3 , otherwise (ii) pnd2(Cn) = { n , n = 3, 4 3 , otherwise Proof. (i) Since pnd(Pn) = n for n = 1, 2, it follows that pnd2(Pn) = n for n = 1, 2. For n = 3, let V (P3) = {v1, v2, v3}. Since pnd(P3) = 2, pnd2(P3) ≥ 2. If pnd2(P3) = 2, then there exists vi ∈ V (P3) such that vi /∈ P , where P is a minimum 2-pointwise non- dominating set of P3 for some i ∈ {1, 2, 3}. Suppose that vi = v1. Then v3 is the only vertex in P such that v1 /∈ NG(v3), which is a contradiction. Similarly, if vi = v3. Now, assume that vi = v2. Observe that vertices v1 and v3 are both adjacent to v2, that is, v1, v3 ∈ NP3(v2), a contradiction. Therefore, pnd2(P3) = 3. Suppose that n ≥ 4. Let V (Pn) = {v1, v2, v3, . . . , vn}. Since pnd(Pn) = 2 for all n ≥ 4, it follows that pnd2(Pn) ≥ 2 for all n ≥ 4. Assume that pnd2(Pn) = 2 for all n ≥ 4. Let Q = {vi, vj} be a minimum 2-pointwise non-dominating set of Pn, where j < i, i, j ∈ {1, 2, . . . , n}. Assume that ⟨Q⟩ is connected. If vi = vn, then vj = vn−1. Thus, vi = vn is the only vertex in Q such that vn−2 /∈ NPn(vi), a contradiction. If vi = v2, then vj = v1. Thus, vj = v1 is the only vertex in Q such that v3 /∈ NPn(vj), a contradiction. Similarly, when vi = vr, where r ∈ {3, 4, . . . , n− 1}. Next, assume that ⟨Q⟩ is disconnected. If dPn(vi, vj) = 2, then there exists vs ∈ V (Pn)\Q such that vs ∈ NPn(vi) ∩ NPn(vj) for some s ̸= i, j, which is a contradiction. Thus, dPn(vi, vj) ≥ 3. Let vk ∈ NPn(vi). Then vj is the only vertex in Q such that vk /∈ NPn(vj), a contradiction. Therefore, pnd2(Pn) ≥ 3 for all n ≥ 4. Now, let S = {v1, v2, v3} ⊆ V (Pn). Let vt ∈ V (Pn)\S, where t ∈ {4, 5, . . . , n}. Then vt /∈ NPn(v1) and vt /∈ NPn(v2). It follows that S is a 2-pointwise non-dominating set of Pn. Consequently, pnd2(Pn) = 3 for all n ≥ 4. (ii) Clearly, pnd2(C3) = 3. Let n = 4 and let V (Cn) = {a1, a2, a3, a4}. Since pnd(C4) = 2, pnd2(C4) ≥ 2. Suppose that pnd2(C4) = 2. Let S be a minimum 2- pointwise non-dominating set of C4. Since 2-pointwise non-dominating is a pointwise J. Hassan, A. Gomorez, L. Laja, E. Ahmad / Eur. J. Pure Appl. Math, 17 (2) (2024), 852-859 857 non-dominating, ⟨S⟩ is connected. Thus, {a1, a2}, {a2, a3}, {a3, a4} or {a1, a4} is the pos- sible set S. If S = {a1, a2}, then a1 is the only vertex in S such that a3 /∈ NCn(a1), a contradiction. Next, suppose that S = {a2, a3}, then a2 is the only vertex in S such that a4 /∈ NC4(a2), a contradiction. Similarly, when S = {a3, a4}, or S = {a1, a4}. Therefore, pnd2(C4) ≥ 3. Suppose that pnd2(C4) = 3. Then there exists ai ∈ V (C4) which is not in 2-pointwise non-dominating set R of C4 for some i ∈ {1, 2, 3, 4}. Assume that ai = a1. However, a3 is the only vertex in R such that ai /∈ NC4(a3), a contradiction. Similarly, when ai = a2, a3 or a4. Consequently, pnd2(C4) = 4. Now, assume that n ≥ 5. Let V (Cn) = {a1, a2, . . . , an} and consider B = {a1, a2, a3}. Then, B is a minimum 2-pointwise non-dominating set of Cn. Thus, pnd2(Cn) = 3 for all n ≥ 5. Theorem 4. Let G and H be two graphs. Then a subset P of a vertex-set of G +H is a 2-hop dominating if and only if P = PG ∪ PH , where PG ⊆ V (G) and PH ⊆ V (H) are 2-pointwise non-dominating sets of G and H, respectively. Proof. Suppose that P is a 2-hop dominating set of G + H. Assume that PG = ∅. Then P = PH ⊆ V (H). Since NG+H [PH ] ⊆ V (H), NG+H [PH ] ̸= V (G + H), which is a contradiction. Therefore, PG ̸= ∅. Similarly, PH ̸= ∅. Now, let x ∈ V (G)\PG. Since P is a 2-hop dominating set in G+H, there exist y, w ∈ PG ⊆ P such that dG+H(x, y) = 2 and dG+H(w, x) = 2. Thus, x /∈ NG(y) and x /∈ NG(w). Hence, PG is 2-pointwise non- dominating set of G. Similarly, PH is a 2-pointwise non-dominating set of H. Conversely, suppose that P = PG ∪ PH , where PG and PH are 2-pointwise non- dominating sets of G andH, respectively. Let a ∈ V (G+H)\P . Then either a ∈ V (G)\PG or a ∈ V (H)\PH . Suppose that a ∈ V (G)\PG. Since PG is a 2-pointwise non-dominating set of G, there exist u, v ∈ PG ⊆ P such that dG(a, u) ≥ 2 and dG(a, v) ≥ 2. It follows that a ∈ N2 G+H [u] and a ∈ N2 G+H [v]. Hence, P is a 2-hop dominating set of G+H. Similarly, when a ∈ V (H)\PH , then P is a 2-hop dominating set of G+H. Corollary 1. Let G and H be two graphs. Then γ2h(G+H) = pnd2(G) + pnd2(H). In particular, each of the following holds: (i) γ2h(Pn + Pm) =  n+m , if 1 ≤ n,m ≤ 3 n+ 3 , if 1 ≤ n ≤ 3 and m ≥ 4 m+ 3 , if 1 ≤ m ≤ 3 and n ≥ 4 6 , if n,m ≥ 4. J. Hassan, A. Gomorez, L. Laja, E. Ahmad / Eur. J. Pure Appl. Math, 17 (2) (2024), 852-859 858 (ii) γ2h(Cn + Cm) =  n+m , if n,m = 3, 4 n+ 3 , if n = 3, 4 and m ≥ 5 m+ 3 , if m = 3, 4 and n ≥ 5 6 , if n,m ≥ 5. (iii) γ2h(Kn +Km) = n+m for all positive integer n,m ≥ 1. (iv) γ2h(Fn) = γ2h(K1 + Pn) = { n+ 1 , if 1 ≤ n ≤ 3 4 , if n ≥ 4 (v) γ2h(Wn) = γ2h(K1 + Cn) = { n+ 1 , if n = 3, 4 4 , if n ≥ 5 Proof. Let P be a minimum 2-hop dominating set of G + H. Then by Theorem 4, P = PG ∪ PH , where PG and PH are 2-pointwise non-dominating sets of G and H, respectively. Thus, pnd2(G) ≤ |PG| and pnd2(H) ≤ |PH |. Hence, γ2h(G+H) = |P | = |PG|+ |PH | ≥ pnd2(PG) + pnd2(PH). On the other hand, let P = PG∪PH , where PG and PH are minimum 2-pointwise non- dominating sets of G and H, respectively. Then by Theorem 4, P is a 2-hop dominating set of G+H. Thus, γ2h(G+H) ≤ |P | = |PG|+ |PH | = pnd2(G)+pnd2(H). Consequently, γ2h(G+H) = pnd2(G) + pnd2(H). Moreover, (i),(ii), (iii),(iv) and (v) follow from Remark 2 and Proposition 1. 4. Conclusion The 2-hop domination parameter has been introduced and initially investigated in this paper. This new parameter is always defined on any simple and undirected graph. Its properties and its connections with hop domination have been presented. Moreover, this parameter has been investigated on the join of two graphs. The 2-hop dominating sets in the join of two graphs have been characterized and used to derive some formulas of the parameter. Interested researchers may further investigate this concept on other graphs that were not considered in this study. They may also consider the possibility of applying this newly defined parameter to another field. Acknowledgements The authors would like to thank Mindanao State University - Tawi-Tawi College of Technology and Oceanography, and Western Mindanao State University for funding this research. REFERENCES 859 References [1] V. Bilar, M.A. Bonsocan, J. Hassan, and S. Dagondon. Vertex cover hop dominating sets in graphs. Eur. J. Pure Appl. Math., 17(1):93–104, 2024. [2] J. Hassan and ASS. Sappari AR. Bakkang. j2-hop domination in graphs: Properties and connections with other parameters. Eur. J. Pure Appl. Math., 16(4):2118–2131, 2023. [3] J. Hassan and S. Canoy. Connected grundy hop dominating sequences in graphs.,. Eur. J. Pure Appl. Math., 16(2):1212–1227, 2023. [4] J. Hassan and S. Canoy Jr. Grundy dominating and grundy hop dominating sequences in graphs: Relationships and some structural properties. Eur. J. Pure Appl. Math., 16(2):1154–1166, 2023. [5] J. Hassan and S. Canoy Jr. Grundy total hop dominating sequences in graphs. Eur. J. Pure Appl. Math., 16(4):2597–2612, 2023. [6] J. Hassan, A. Lintasan, and N.H. Mohammad. Some properties and realization prob- lems involving connected outer-hop independent hop domination in graphs. Eur. J. Pure Appl. Math., 16(3):1848–1861, 2023. [7] A.Y. Isahac, J. Hassan, LS. Laja, and HB. Copel. Outer-convex hop domination in graphs under some binary operations. Eur. J. Pure Appl. Math., 16(4):2035–2048, 2023. [8] S. Canoy Jr. and J. Hassan. Weakly convex hop dominating sets in graphs. Eur. J. Pure Appl. Math., 15(4):1783–1796, 2022. [9] J. Manditong, J. Hassan, LS Laja, AA. Laja, NHM. Mohammad, and SU. Kam- don. Connected outer-hop independent dominating sets in graphs under some binary operations. Eur. J. Pure Appl. Math., 16(3):1817–1829, 2023. [10] J. Manditong, A. Tapeing, J. Hassan, A.R. Bakkang, N.H. Mohammad, and S.U. Kamdon. Some properties of zero forcing hop dominating sets in a graph. Eur. J. Pure Appl. Math., 17(1):324–337, 2024. [11] J. Mohamad and H. Rara. On resolving hop domination in graphs. Eur. J. Pure Appl. Math., 14(1):324–337, 2021. [12] C. Natarajan and S. Ayyaswamy. Hop domination in graphs ii. Versita., 23(2):187– 199, 2015.