EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS 2025, Vol. 18, Issue 1, Article Number 5625 ISSN 1307-5543 – ejpam.com Published by New York Business Global Characterizing 2-Distance Certified Hop Dominating Sets Using Co-Certified Pointwise Non-domination Concept Noor-Sharief N. Ulal1, Javier A. Hassan1,2,∗, Mercedita A. Langamin1, Noor-Han N. Ulal1 1Mathematics and Sciences Department, College of Arts and Sciences, MSU Tawi-Tawi College of Technology and Oceanography, Bongao, Tawi-Tawi, Philippines 2Department of Mathematics, College of Science, Korea University, Seoul, South Korea Abstract. Let G be a graph. Then C ⊆ V (G) is called a 2-distance certified hop dominating if ∀ x ∈ V (G)\C, there exists y ∈ C such that dG(x, y) = 2 and ∀ a ∈ C, |N2 G(a)\C| = 0 or |N2 G(a)\C| ≥ 2. The 2-distance certified hop domination number of G, denoted by γ2ch(G), is the minimum cardinality among all 2-distance certified hop dominating sets of G. In this study, the researchers give some properties of this new concept on some graphs, and present some its connections with others parameters. Also, the researchers introduce co-certified pointwise non- domination (co-certified pnd) to characterize the 2-distance certified hop dominating sets in the join of two graphs. They obtain some simplified formulas of the said parameter on this graph using this newly defined concept and some characterizations formulated. 2020 Mathematics Subject Classifications: 05C69 Key Words and Phrases: 2-distance certified set, co-certified pointwise non-domination, 2- distance certified hop dominating set, 2-distance certified hop domination number 1. Introduction Domination in graph theory is a fundamental concept that explores how subsets of vertices can control or influence the entire graph. A dominating set for a graph G is defined as a subset of vertices D such that every vertex in G is either included in D or is adjacent to at least one vertex in D. This concept is crucial in various applications such as in network design, resource allocation, social network analysis, and in infrastructure networks. ∗Corresponding author. DOI: https://doi.org/10.29020/nybg.ejpam.v18i1.5625 Email addresses: noor-shariefulal@msutawi-tawi.edu.ph (N.S. Ulal) javierhassan@msutawi-tawi.edu.ph (J. Hassan) merceditalangamin@msutawi-tawi.edu.ph (M. Langamin) noorhanulal@msutawi-tawi.edu.ph (N.H. Ulal) https://www.ejpam.com 1 Copyright: © 2025 The Author(s). (CC BY-NC 4.0) N. S. Ulal et al. / Eur. J. Pure Appl. Math, 18 (1) (2025), 5625 2 of 9 The study of domination encompasses various parameters, including the domination number, which is the minimum size of a dominating set, and different types or variants of domination such as certified domination [5], Grundy hop domination variants [8, 9], convex hop domination [7], double domination [6], and many more. Each variation provides unique insights and tools for addressing specific problems within graphs. Some interesting studies related to domination, certified domination, and hop domination can be found in [1–4, 10, 11]. In this paper, new parameter called 2-distance certified hop domination in a graph is introduced and investigated. The researchers believe that his parameter and its re- sults would give additional insights to researchers in the field and would lead to another interesting topics or network application in the future. 2. Terminology and Notation Let G = (V (G), E(G)) be a simple and undirected graph. The distance dG(u, v) in G of two vertices u, v is the length of a shortest u-v path in G. The greatest distance between any two vertices in G, denoted by diam(G), is called the diameter of G. Two vertices x, y of G are adjacent, or neighbors, if xy is an edge of G. The open neighborhood of x in G is the set NG(x) = {y ∈ V (G) : xy ∈ E(G)}. The closed neighborhood of x inG is the setNG[x] = NG(x)∪{x}. IfX ⊆ 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 subset S of V (G) is called a dominating set of G if for every a ∈ V (G)\S, there exists b ∈ S such that dG(a, b) = 1, that is, S is a dominating set of G if NG[S] = V (G). The minimum cardinality among all dominating sets of G, denoted by γ(G), is called the domination number of G. A dominating set S ⊆ V (G) is called a certified dominating set of G if every a ∈ S, a has either zero or atleast two neighbors in V (G) \ S. The minimum cardinality among all certified dominating sets of G, denoted by γcer(G), is called the certified domination number of G. Let G be a graph. Then S ⊆ V (G) is called a pointwise non-dominating (pnd) set of G if for each v ∈ V (G)\S, there exists w ∈ S such that v /∈ NG(w). The minimum cardinality of a pointwise non-dominating (pnd) set of G, is called the pointwise non-domination (pnd) number of G. 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, that is, S is a hop dominating set of G if N2 G[S] = V (G). The minimum cardinality among all hop dominating sets of G, denoted by γh(G), is called N. S. Ulal et al. / Eur. J. Pure Appl. Math, 18 (1) (2025), 5625 3 of 9 the hop 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 4. Properties and Bounds of 2-Distance Certified Hop Domination in Some Graphs Definition 1. Let G be a graph. Then a set C ⊆ V (G) is called a 2-distance certified hop dominating if ∀ x ∈ V (G)\C, there exists y ∈ C such that dG(x, y) = 2 and ∀ a ∈ C, |N2 G(a)\C| = 0 or |N2 G(a)\C| ≥ 2. The 2-distance certified hop domination number of G, denoted by γ2ch(G), is the minimum cardinality among all 2-distace certified hop dominating sets of G. Example 1. Below is an example of 2-distance certified hop domination. P5 : a b c d e Figure 1: A path graph of P5 with γ2ch(P5) = 3 Consider the Path graph given above. Let C = {b, c, d}. Then N2 G[b] = {b, d}, N2 G[c] = {a, c, e} and N2 G[d] = {b, d}. Thus, N2 G[C] = V (G), and so C is a hop dominating set of G. Observe that, vertices b and d have zero hop neighbor in V (G)\C and vertex c has two hop neighbors a, e in V (G)\C. Therefore, C is a 2-distance certified hop dominating set of G. Moreover, it can be verified that γ2ch(G) = 3. Theorem 1. Let G be a graph. Then (i) γh(G) ≤ γ2ch(G) (ii) 1 ≤ γ2ch(G) ≤ |V (G)| (iii) γ2ch(G) = 1 if and only if G = K1 Proof. (i) Let D be a minimum 2-distance certified hop dominating set of G. Then D is a hop dominating set of G and γ2ch(G) = |D|. Thus, γh(G) ≤ |D| = γ2ch(G) by definition. (ii) Since γh(G) ≥ 1 for any graph (G), γ2ch(G) ≥ 1 by (i). The upperbound is clear since any 2-distance certified hop dominating set is always a subset of V (G). N. S. Ulal et al. / Eur. J. Pure Appl. Math, 18 (1) (2025), 5625 4 of 9 (iii) Suppose that γ2ch(G) = 1. Then γh(G) = 1 by (i). It follows that G = K1. Conversely, Suppose that G = K1. Then by (ii) γ2ch(G) = 1 Theorem 2. Let n be a positive integer. Then S ⊆ V (Kn) is a 2-distance certified hop dominating set if and only if S = V (Kn). Proof. Suppose that S is 2-distance certified hop dominating of Kn. Assume that S ̸= V (Kn). Then there exists at least one vertex v ∈ V (Kn) such that v /∈ S. Since the graph is complete, it implies that every vertex is adjacent to every other vertex. Then for S to be a 2-distance certified hop dominating, v must be included in S. Since v /∈ N2 G[S], a contradiction. For the converse, suppose that S = V (Kn). Then S is a 2-distance certified hop dominating set of Kn. Corollary 1. Let m be a positive integer. Then γ2ch(Km) = m for all m ≥ 1. 5. Co-Certified Pointwise Non-Domination in Graphs The following definiton will be used to characterize the 2-distnace certified hop domi- nating sets in the join of two graphs as well as to solve its 2-distance certified hop domi- nation numbers. Definition 2. Let G be a graph. Then S ⊆ V (G) is called a co-certified pointwise non-dominating (co-certified pnd) set of G if S satisfies the following two conditions: (i) For each u ∈ S, there exist either zero or at least two vertices x, y ∈ V (G)\S such that x, y /∈ NG(u). (ii) For each v ∈ V (G)\S, there exists w ∈ S such that v /∈ NG(w). The minimum cardinality of a co-certified pointwise non-dominating (co-certified pnd) set of G, is called the co-certified pointwise non-domination (co-certified pnd) number of G. Remark 1. Let G be a graph. Then (i) pnd(G) ≤ ccpnd(G); and (ii) 1 ≤ ccpnd(G) ≤ |V (G)|. Theorem 3. Let G be a graph. Then ccpnd(G) ̸= |V (G)| if and only if ccpnd(G) ≤ |V (G)| − 2. Proof. Suppose that ccpnd(G) = |V (G)| − 1, say S is the minimum co-certified pnd set. Then there exists x ∈ V (G) such that x /∈ S. Let y ∈ S. If x and y are non-adjacent. N. S. Ulal et al. / Eur. J. Pure Appl. Math, 18 (1) (2025), 5625 5 of 9 Then x /∈ NG(y). That is, y has only one non-neighbor x in V (G)\S, a contradiction. Therefore, the assertion follows. The converse is clear. Proposition 1. Let k be a positive integer. Then, (i) ccpnd(Pk) = { k, if k = 1, 2, 3, 4 2, if k ≥ 5; (ii) ccpnd(Ck) = { k, if k = 3, 4 2, if k ≥ 5; (iii) ccpnd(Kk) = k for all k ≥ 1; and (iv) ccpnd ¯(Kk) = { 1, if for all k ≥ 3 k, if k = 1, 2. Proof. (i) Since pnd(Pk) = k for k = 1, 2, it follows that ccpnd(Pk) = k for k = 1, 2 by Remark 1. For k = 3, let V (P3) = {a1, a2, a3}. Consider R = {a1, a2}. Then R is a minimum pnd set of P3, and so by Remark 1, ccpnd(P3) ≥ 2. By Theorem 3, ccpnd(P3) = 3. For k = 4, let V (P4) = {a1, a2, a3, a4}. Consider Q = {a1, a2}. Then Q is a minimum pnd set of P4. Thus, ccpnd(P4) ≥ 2 by Remark 1. Suppose that ccpnd(G) = 2, say M is a minimum co-certified pnd set of P4. Then M is either of the following sets: {a1, a2}, {a2, a3}, {a3, a4} or {a1, a4}. However, either of these cases contradicts our assumption of being a co-certified pnd set of P4. Therefore, by Theorem 3, ccpnd(P4) = 4. Next, for k ≥ 5, let V (Pk) = {v1, v2, ..., vk}. Consider N = {v1, v2}. Then N is a minimum pnd set of Pk. Since k ≥ 5, both v1 and v2 has at least two non-neighbors in V (Pk)\N , respectively. Therefore, N is a minimum co-certified pnd set of Pk, and so ccpnd(Pk) = 2 for all k ≥ 5. (ii) Since pnd(C3) = 3, it follows that ccpnd(C3) = 3 by Remark 1. For n = 4, let V (C4) = {u1, u2, u3, u4}. Consider Q = {u1, u2}. Then Q is a minimum pnd set of C4. By Remark 1, ccpnd(C4) ≥ 2. Suppose that ccpnd(C4) = 2, say R is a minimum co-certified pnd set of C4. Then R is either of the following sets: {u1, u2}, {u2, u3}, {u3, u4} or {u4, u1}. However, either of these cases violates the properties of a co-certified pnd set. By Theorem 3, ccpnd(C4) = 4. Now, suppose that k ≥ 5. Let V (Ck) = {u1, u2, ..., uk}. Consider P = {u1, u2}. Then P is a minimum pnd set of Ck. Since k ≥ 5, u1 and u2 has at least two neighbors in V (Ck)\P . Therefore, P is a minimum co-certified pnd set of Ck, and so ccpnd(Ck) = 2 for all k ≥ 5. N. S. Ulal et al. / Eur. J. Pure Appl. Math, 18 (1) (2025), 5625 6 of 9 (iii) Let S = V (Kk) = {a1, a2, ..., ak}. Then S is a co-certified pnd set of Kk. Suppose that S is not a minimum co-certified pnd set of Kk. Then there exists x ∈ V (Kk) such that x /∈ S. However, x is adjacent to every other vertex in V (Kk)\{x}, a contradiction to the fact that S is a pnd set of Kk. Therefore, S = V (Kk) is a minimum co-certified pnd set of Kk, and so ccpnd(Kk) = k ∀ k ≥ 1 (iv) Clearly, ccpnd ¯(Kk) = 1. For k = 2, let V ¯(Kk) = {v1, v2}. Consider R = {v1}. Then R is a minimum pnd set of ¯(K2), and so pnd ¯(K2) = 1. Thus, ccpnd ¯(K2) ≥ 1. Assume that ccpnd ¯(K2) = 1. Then either {v1} or {v2} is a minimum co-certified pnd set of K̄2. Suppose that M = {v2} is a minimum co-certifed pnd set of ¯(K2). However, v2 has only one non-neighbor v1 ∈ V ¯(K2)\M , a contradiction. Similarly the assertion follows when M = {v1}. Thus, ccpnd ¯(K2) = 2. Next, suppose that k ≥ 3. Let V ¯(Kk) = {a1, a2, ..., ak}. Consider B = {a1}. Then B is a minimum pnd set of ¯(Kk). Since k ≥ 3, a1 has at least two non-neighbors in V (K̄) \B. Therefore, ccpnd ¯(Kk) = 1 for all k ≥ 3. 6. 2-Distance Certified Hop Domination in the Join of Two Graphs Theorem 4. Let G and H be graphs. Then O ⊆ (G + H) is a 2-distance certified hop dominating set of G+H if and only if O = OG ∪OH , where OG and OH are co-certified pnd sets in G and H, respectively. Proof. Suppose that O ⊆ V (G + H) is a 2-distance certified hop dominating set of G +H. Then O is a hop dominating set of G +H. If O ⊆ V (G), then N2 G[O] ⊆ V (G), a contradiction. Hence, O ⊈ V (G). Similarly, O ⊈ V (H). Thus, O = OG ∪ OH , where OG ⊆ V (G) and OH ⊆ V (H). Let x ∈ V (G + H)\O. Assume that x ∈ V (G)\OG. Since O is a hop dominating, there exists y ∈ O such that dG+H(x, y) = 2. It follows that x /∈ NG(y), and so OG is a pnd set of G. Since O is a 2-distance certified set, for every w ∈ OG, there exist either zero or at least two vertices u, v ∈ V (G)\OG such that dG+H(w, u) = (w, v) = 2. Hence, u, v /∈ NG(w). Consequently, OG is a co-certified pnd set of G. Similarly, OH is a co-certified pnd set of H. Conversely, suppose that O = OG ∪ OH , where OG and OH are co-certified pnd sets in G and H, respectively. Let a ∈ V (G+H)\O. Assume that a ∈ V (G)\OG. Since OG is a co-certified pnd set of G, there exists b ∈ OG such that a /∈ NG(b) and for each q ∈ OG, there exist either zero or at least two neighbor r, t ∈ V (G)\OG such that r, t /∈ NG(q). This means that dG+H(a, b) = 2 and q has either zero or at least two hop neighbors r, t ∈ G +H. Thus, O is a 2-distance certified hop dominating set of G +H. Similarly, when a ∈ V (H)\OH , then O is a 2-distance certified hop dominating set of G+H. Theorem 5. Let G and H be a graphs. Then γ2ch(G+H) = ccpnd(G) + ccpnd(H). Proof. Suppose that O = OG ∪OH is a minimum 2-distance certified hop dominating set of G + H. Then by Theorem 4, OG and OH are co-certified pnd sets of G and H, N. S. Ulal et al. / Eur. J. Pure Appl. Math, 18 (1) (2025), 5625 7 of 9 respectively. Thus, γ2ch(G+H) = |O| = |OG|+ |OH | ≥ ccpnd(G) + ccpnd(H) (i) On the other hand, suppose that O = OG∪OH , where OG and OH are both minimum co-certified pnd sets of G and H, respectively. Then by Theorem 4, O is a 2-distance certified hop domknating set of G+H. Therefore, ccpnd(G) + ccpnd(H) = |OG|+ |OH | = |O| ≥ γ2ch(G+H) (ii) Combining (i) and (ii), we have γ2ch(G+H) = ccpnd(G) + ccpnd(H). The following result follows from Proposition 1 and Theorem 5. Corollary 2. Let n be a positive integer. Then (i) γ2ch(Pn + Pn) = { 2n, if n = 1, 2, 3, 4 4, if n ≥ 5; (ii) γ2ch(Cn + Cn) = { 2n, if n = 3, 4 4, if n ≥ 5; (iii) γ2ch(Kn +Kn) = 2n for all n ≥ 1; (iv) γ2ch(Sn) = { n, if n = 1, 2 2, if n ≥ 3; (v) γ2ch(Km,n) =  4, if m,n = 2 3, if m = 2 and n ≥ 3 or m ≥ 3 and n = 2 2, if m,n ≥ 3 or m, n = 1; (vi) γ2ch(F1,n) = { n+ 1, if n = 1, 2, 3, 4 3, if n ≥ 5; and (vii) γ2ch(Wn) = { n+ 1, if n = 3, 4 3, if n ≥ 5. 7. Incomparability of 2-distance certified hop domination with certified domination Remark 2. Let H be any graph. Then certified domination and 2-distance certified hop domination parameters are incomparable. Consider the graph G below. N. S. Ulal et al. / Eur. J. Pure Appl. Math, 18 (1) (2025), 5625 8 of 9 a b c d e f g h i k j l m G : Let S1 = {a, e, h, k,m} and S2 = {c,m}. Then S1 is minimum certified dominating set of (G). Thus γcer(G) = 5. Moreover, S2 is minimum 2-distance certified hop dominating set of G. Hence, γ2ch(G) = 2. Therefore, γcer(G) > γ2ch(G). Next, consider the graph G′ below. a b c G′ : d e Let U1 = {a, b} and U2 = {a, b, d}. Then U1 is minimum certified dominating set of G′. Thus, γcer = 2. Additionally, U2 is minimum 2-distance certified hop dominating set of G′. Hence, γ2ch = 3. Therefore, γcer < γ2ch. Acknowledgements The authors would like to thank Mindanao State University - Tawi-Tawi College of Technology and Oceanography, and Korea University for funding this research. Also, the authors would like to thank the referees for their invaluable comments and suggestions that led to the improvement of the paper. References [1] V. G. Bhagavathi Ammal and R. Louisa Dickfania. Accurate certified domination number of graphs. International Journal of Mathematics Trends and Technology, N. S. Ulal et al. / Eur. J. Pure Appl. Math, 18 (1) (2025), 5625 9 of 9 66(05):90–98, 2020. [2] S. Ayyaswamy, B. Krishnakumari, B. Natarjan, and Y. Venkatakrishnan. Bounds on the hop domination number of a tree. Proceedings-Mathematical Sciences, 125(4):449–455, 2015. [3] V. Bilar, M. A. Bonsocan, J. Hassan, and S. Dagondon. Vertex cover hop dominating sets in graphs. European Journal of Pure and Applied Mathematics, 17(1):93–104, 2024. [4] E. J. Cockayne and S. T. Hedetniemi. Towards a theory of domination in graphs. Networks, 7(3):247–261, 1977. [5] M. Dettlaff, M. Lemanska, R. Ziemann, J. Topp, and P. Zylinski. Certified dom- ination. AKCE International Journal of Graphs and Combinatorics, 09(004):1–12, 2018. [6] F. Harary and T. W. Haynes. Double domination in graphs. Ars Combinatoria, 55:201–213, 2000. [7] J. Hassan, S. Canoy, and C. J. Saromines. Convex hop domination in graphs. Euro- pean Journal of Pure and Applied Mathematics, 16(1):319–335, 2023. [8] J. Hassan and S. Canoy Jr. Grundy dominating and grundy hop dominating sequences in graphs: Relationships and some structural properties. European Journal of Pure and Applied Mathematics, 16(2):1212–1227, 2023. [9] J. Hassan and S. Canoy Jr. Grundy total hop dominating sequences in graphs. European Journal of Pure and Applied Mathematics, 16(4):2597–2612, 2023. [10] C. Natarajan and S. Ayyaswamy. Hop domination in graphs ii. Versita, 23(2):187– 199, 2015. [11] S. Durai Raj, S. G. Shiji Kumari, and A. M. Anto. Certified domination number in corona product of graphs. Malaya Journal of Matematik, 9(1):1080–1082, 2021.