EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS 2025, Vol. 18, Issue 1, Article Number 5555 ISSN 1307-5543 – ejpam.com Published by New York Business Global Edge Geodetic Dominating Sets of Some Graphs Clint Joy M. Quije1,2, Rochelleo E. Mariano3, Eman C. Ahmad3,∗ 1 Mathematics Department, College of Science and Information Technology, Ateneo De Zamboanga University, Zamboanga City, Philippines 2 Institute of Arts and Sciences, Tangub City Global College, Tangub City, Philippines 3 Department of Mathematics and Statistics, College of Science and Mathematics, Western Mindanao State University, Zamboanga City, Philippines Abstract. Let G be a simple graph. A subset D of vertices in G is a dominating set of G if every vertex not in D has at least one neighbor in D. The domination number γ(G) of G is the minimum cardinality of a dominating set of G. An edge geodetic set of G is a set S ⊆ V (G) such that every edge of G is contained in a geodetic joining some pair of vertices in S. The edge geodetic number ge(G) of G is the minimum cardinality of edge geodetic set. A set of vertices S in G is an edge geodetic dominating set of G if S is both an edge geodetic set and a dominating set. The minimum cardinality of an edge geodetic dominating set of G is its edge geodetic domination number and is denoted by γge(G). In this study, we determined the edge geodetic domination number of graphs obtained through the deletion of independent edges of complete graphs and graphs resulting from the Kr-gluing of complete graphs. It is also shown that for any positive integers 2 ≤ a ≤ b, there exists a connected graph G such that ge(G) = a and γge(G) = b. 2020 Mathematics Subject Classifications: 05C69, 05C76 Key Words and Phrases: Dominating Set, Domination Number, Edge geodetic, Complete Graphs, Deletion of Independent Edges, Kr-gluing, Realization Result or Result of Comprehension 1. Introduction Several studies have been conducted regarding geodetic sets, geodetic bounds and edge geodetic sets in graphs. Asdain et al. [1], Chartrand et al. [3], Mariano and Canoy [8], and Santhakumaran and John [12], are some researchers who have done many results in this area. The results include determining the geodetic and edge geodetic number of graphs employing the unary and binary operations in graphs such as, the deletion of independent edges of complete graphs, Kr-gluing, join, corona, composition, and cartesian products of graphs, among others. ∗Corresponding author. DOI: https://doi.org/10.29020/nybg.ejpam.v18i1.5555 Email addresses: cjquije@gadtc.edu.ph (C.J. Quije), mariano.rochelleo@wmsu.edu.ph (R. Mariano), ahmad.eman@wmsu.edu.ph (E. Ahmad) https://www.ejpam.com 1 Copyright: © 2025 The Author(s). (CC BY-NC 4.0) C.J. Quije, R. Mariano, E. Ahmad / Eur. J. Pure Appl. Math, 18 (1) (2025), 5555 2 of 8 Besides geodetic set and edge geodetic sets in graphs, there are also a lot of studies done due to dominating sets in graphs. In [13], it was defined that a subset D of vertices in G is called dominating set if every vertex not in D has at least one neighbor in D. The domination number γ(G) of G is the minimum cardinality of a dominating set of G. The notion of domination for some classes of graphs were studied by Castaneda et. al in [2]. They considered variations of the concept of domination in a graph. With the extensive results on the above-mentioned graph invariants, a number of researchers have ventured into making an offshoot of the study. As a consequence, the concept of geodetic domination in graphs has been coined. Apparently, this has been extended to the thought of the edge geodetic domination in graphs. Due to the former, there have been quite a number of results that were generated from the geodetic domination in graphs. Escuadra et al. [4], Vijayan et al. [15] are among those researchers who have contributed significant results in this endeavor. Only very few, however, have undergone studies on the edge geodetic domination in graphs. Stalin et al. [13] and Samodivkin [9], made some results on the edge geodetic domination in graphs. There were results with some realizations done for the edge geodetic dominating number of graphs. A number of these results were preliminaries that include edge geodetic dominating number of (special) graph in unary operation. Note, however, that the edge geodetic dominating number in the binary operation of graphs is not that extensive yet. Though there were attempts to explore on this area but the amount of results done is still meager. To cite a few, Stalin et al. [13] in their article, ”Edge Geodetic Dominations in Graphs”, determined the Edge geodetic number of certain classes of graphs. Necessary conditions for connected graphs of order p with edge geodetic domination number p or p-1 are given. They also had shown that for every two integers a, b ≥ 2 with 2 ≤ a < b and b− a− 1 > 0, there is a connected graph G such that γg(G) = a and γg1(G) = b, where γg(G) is the geodetic domination number of a graph. Since limited results are done on the edge geodetic dominating number of some graphs, it is in this regard that a revisit to the foregoing topic was undertaken and some results were generated. In doing this study, the following terminologies from [1–15] are necessary. A simple graph G(V,E) is an undirected graph without loops or multiple edges. V (G) and E(G) denote the vertex and the edge sets of a graph G, respectively. Let S ⊆ V (G). The induced subgraph ⟨S⟩ of G is the graph ⟨S⟩ with vertex set S and edge set {xy ∈ E(G)|x, y ∈ S}. The maximum degree of G, denoted by ∆(G) is given by ∆(G) = max{degG(v) : v ∈ V (G)}. The open neighborhood of the vertex v in a graph G is the set N(v) = {u ∈ V (G) : uv ∈ E(G)}. The closed neighborhood of v is N [v] = N(v) ∪ {v}. A subset D of vertices in G is called dominating set if every vertex not in D has at least one neighbor in D. The domination number γ(G) of G is the minimum cardinality of a dominating set of G. A geodetic set of G is a set S ⊆ V (G) such that every vertex of G is contained in a geodesic joining some pair of vertices in S. The geodetic number g(G) of G is the minimum order of its geodetic sets and any geodetic set of order g(G) is a geodetic basis. An edge geodetic set of G is a set S ⊆ V (G) such that every edge of G is contained in a geodesic joining some pair of vertices in S. The edge geodetic number ge(G) of G is the C.J. Quije, R. Mariano, E. Ahmad / Eur. J. Pure Appl. Math, 18 (1) (2025), 5555 3 of 8 minimum order of its edge geodetic sets and any edge geodetic set of order ge(G) is an edge geodetic basis of G or a ge-set of G. A set of vertices S in G is called a geodetic dominating set of G if S is both geodetic set and a dominating set. The minimum cardinality of a geodetic dominating set of G is its geodetic domination number and is denoted by γg(G). An geodetic dominating set of size γg(G) is said to be a γg-set. Let G be a connected graph. A set of vertices S in G is called an edge geodetic dominating set of G if S is both edge geodetic set and a dominating set. The minimum cardinality of an edge geodetic dominating set of G is its edge geodetic domination number and is denoted by γge(G). An edge geodetic dominating set of size γge(G) is said to be a γge-set. A vertex v is an extreme vertex of a graph G if the subgraph induced by its neighbors is complete. The set of all extreme vertices of G is denoted by Ext(G). A vertex v in a connected graph G is said to be a semi-extreme vertex if it has a neighbor, say u, with N [v] ⊆ N [u]. The set of all semi-extreme vertices of G is denoted by Se(G). A cutvertex of a connected graph G is the vertex whose deletion increases the number of components of the subgraph of G, that is, u is a cutvertex if and only if ⟨G− u⟩ is disconnected. The deletion or removal of a proper subset S of vertices of G results in that subgraph G \ S of G consisting of all vertices of G not in S and all edges not incident with a vertex in S. The deletion of a vertex u of G results in that subgraph G \ u of G consisting of all vertices of G except u and all edges not incident with a vertex u. On the other hand, the deletion of a subset X of edges yields the spanning subgraph G \X containing all edges of G not in X. Let G1, G2, . . . , Gt be disjoint graphs each containing a complete subgraph Kr (r ≥ 1). Let G be the graph obtained from the union of t graphs Gi by identifying the Kr’s (one from each Gi) in an arbitrary way. We call G a Kr-gluing of G1, G2, . . . , Gt. In particular, when r = 1 (respectively r = 2) we say G is a vertex-gluing (respectively an edge-gluing) of G1, G2, . . . , Gt. 2. Preliminaries The following are the known results related to this study. Remark 1. [8] Let G be a nontrivial connected graph. Then V (G) is an edge geodetic dominating set of G. Theorem 1. [13] If G has at least two vertices of degree n− 1, then γge(G) = n Theorem 2. [13] For the complete graph Kn with n ≥ 2, γge(Kn) = n. Theorem 3. [12] Each extreme vertex of G belongs to every edge geodetic cover of G. In particular, each end vertex of G belongs to every edge geodetic cover of G Theorem 4. [13] If G has exactly one vertex of degree n− 1, then γge(G) = n− 1. C.J. Quije, R. Mariano, E. Ahmad / Eur. J. Pure Appl. Math, 18 (1) (2025), 5555 4 of 8 3. Main Results 3.1. Deletion of Independent Edges of Complete Graphs Theorem 5. Let G be a complete graph of order n ≥ 4. Let S ⊆ V (H), where H is a connected subgraph of G obtained by deleting m ≤ ⌊n2 ⌋ independent edges in G. i. If m < ⌊n2 ⌋, then S is an edge geodetic dominating set of H if and only if S = V (H). ii. If m = ⌊n2 ⌋ and n is odd, then S is an edge geodetic dominating set of H if and only if S = V (H) \ {v} or S = V (H), v is the vertex of degree n− 1 in H. iii. If m = ⌊n2 ⌋ and n is even, then S is an edge geodetic dominating set of H if and only if S = V (H) \ {u, v} or S = V (H) \ {v} or S = V (H) \ {u} or S = V (H), where vertices u and v are not adjacent in H. Proof. Let G be a complete graph of order n ≥ 4. Suppose H is a connected subgraph of G obtained by deleting m independent edges in G. If 1 ≤ m < ⌊n2 ⌋, then the subgraph H contains two or more vertices v with ∆ (⟨N(v)⟩) = |N(v)| − 1 for all v ∈ V (H). By Theorem 1 and Remark 1, S is an edge geodetic dominating set of H if and only if S = V (H). This proves (i). If m = ⌊n2 ⌋ and n is odd, then m = ⌊n2 ⌋ = n−1 2 . Hence, the subgraph H contains a unique vertex v ∈ V (H) such that degG(v) = n− 1. Thus, by Remark 1, Theorem 1 and Theorem 3, S is an edge geodetic set of H and consequently, an edge geodetic dominating set of H if and only if S = V (H) \ {v} or S = V (H), where v is the vertex of degree n− 1 in H. This proves (ii). Suppose m = ⌊n2 ⌋ and n is even. Consider a pair (u, v) of vertices in H such that u is not adjacent to v in H. Then we claim that S = V (H)\{u, v} is a minimum edge geodetic dominating set. To prove this claim, let x, y ∈ V (H) such that xy ∈ E(H) and consider the following cases: Case 1. Suppose x, y ∈ S. Then xy is contained in the x− y geodesic. Case 2. Suppose x = u or x = v and y ∈ S. Without loss of generality, assume x = u. Pick z ∈ V (H) \ {y} such that zy /∈ E(H). Then uz ∈ E(H). Therefore, [z, u, y] is a z − y geodesic containing uy ∈ E(H). Hence, S = V (H) \ {u, v}, where uv /∈ E(H), is an edge geodetic set. In addition, y ∈ S is adjacent to u and v, hence, S is an edge geodetic dominating set. Next, let D ⊆ V (H) and let T = V (H) \ D, where |D| ≥ 3 or ⟨D⟩ contains K2. By definition of independent edges, there exists u, v ∈ D such that uv ∈ E(H). Then there exist a unique a and a unique b in S such that au, vb /∈ E(H). Since ux ∈ E(H) for all x ∈ V (H) \ {a} and vz ∈ E(H) for all z ∈ V (H) \ {b}, it follows that [u, v], [a, v, u] and [b, u, v] are the only geodesics containing uv. Thus, T is not an edge geodetic set of H. Therefore, S is an edge geodetic dominating set of H if and only if S = V (H) \ {u, v} or S = V (H) \ {v} or S = V (H), where vertices u and v are not adjacent in H. This proves (iii). C.J. Quije, R. Mariano, E. Ahmad / Eur. J. Pure Appl. Math, 18 (1) (2025), 5555 5 of 8 Corollary 1. Let G be a complete graph of order n. If H is a connected subgraph of G obtained by deleting m independent edges in G, then γge(H) =  n if m < ⌊n2 ⌋ n− 1 if m = ⌊n2 ⌋ and n is odd n− 2 if m = ⌊n2 ⌋ and n is even 3.2. Kr-gluing of Complete Graphs Theorem 6. Let p, q, r be positive integers such that 1 ≤ r ≤ p ≤ q. Let G be the Kr-gluing of Kp and Kq and S ⊆ V (G). i If 1 = r < p ≤ q, then S = V (G)\V (Kr) is the edge geodetic dominating basis of G. ii If 1 < r < p ≤ q, then V (G) is the edge geodetic dominating basis of G. iii If 1 < r = p ≤ q, then V (G) is the edge geodetic dominating basis of G. Proof. i Since V (Kr) = {v}, then all the elements of Kp \ {v} and Kq \ {v} are neighbors of v in G. This implies that v is the only vertex in G with degG(v) = |V (G)| − 1. Thus, by Theorem 4, γge(G) = |V (G)| − 1 with V (G) \ {V (Kr)} is the unique edge geodetic dominating basis of G. ii If 1 < r < p ≤ q, then every vertex v ∈ V (Kr) has degree |V (G)| − 1. Since |V (Kr)| = r > 1, then G contains more than one vertex of degree |V (G)|−1. Hence, by Theorem 1, γge(G) = |V (G)| and V (G) is the edge geodetic dominating basis of G. iii If 1 < r = p ≤ q, then G = Kq. Since Kq is a complete graph, by Theorem 2, γge(G) = |V (G)| with V (G) as the edge geodetic dominating basis of G. Corollary 2. Let p, q, r be positive integers such that 1 ≤ r ≤ p ≤ q. Let G be the Kr-gluing of Kp and Kq and S ⊆ V (G), then γge(G) =  |V (G)| − 1 if 1 = r < p ≤ q |V (G)| if 1 < r < p ≤ q |V (G)| if 1 < r = p ≤ q 3.3. Result of Comprehension Theorem 7. For any positive integers 2 ≤ a ≤ b, there exists a connected graph G such that ge(G) = a and γge(G) = b. C.J. Quije, R. Mariano, E. Ahmad / Eur. J. Pure Appl. Math, 18 (1) (2025), 5555 6 of 8 Proof. If a = b, consider the complete graph G = Ka. Then by Theorem 2, γge(G) = a. If 2 = a < b with ge(G) = 2 and γge(G) = 3, consider the path P : u1, u2, . . . , u7. For b ≥ 4, letG be the graph obtained from the path on seven vertices P : u1, u2, . . . , u7 by adding (b− 3) sets of three new vertices vij , namely, {v11, v21, v31}, {v12, v22, v32}, . . . , {v1(b−3), v2(b−3), v3(b−3)} for i = 1, 2, 3 and 1 ≤ j ≤ b − 3, with the paths P1 : u2, v11, v21, v31, u6, P2 : u2, v12, v22, v32, u6, . . . , P(b−3) : u2, v1(b−3), v2(b−3), v3(b−3), u6 such that vik is not adjacent to vij , where j ̸= k and j, k = 1, 2, 3, . . . , b− 3. The graph is shown in Figure 1. Figure 1: A graph G From the figure, {u1, u7} is the edge geodetic basis of G, so that ge(G) = 2. Moreover, since {u1, u7} is an edge geodetic basis, we need to include this to any edge geodetic dominating basis of G. In addition, u2 and u6 are dominated by u1 and u7, respectively. Thus, we are left with u3, u4, u5 and vij for i = 1, 2, 3 and 1 ≤ j ≤ b − 3 which are nondominated vertices. To get the minimum cardinality of an edge geodetic dominating set, we have to choose those vertices at the center, hence, we pick u4 and v2j(1 ≤ j ≤ b− 3). Therefore, γge(G) = ge(G) + (b− 3) + 1 = 2 + b− 3 + 1 = b. If 2 < a < b, for b = a+1, consider the graph obtained from the path on eight vertices P : u1, u2, u3, . . . , u8 by adding a− 2 vertices, w1, w2, . . . wa−2 and joining each wi(1 ≤ i ≤ a−2) with u3. However, for b > a+1, let G be the graph obtained from the path on eight vertices P : u1, u2, u3, . . . , u8 by adding a−2 vertices, w1, w2, . . . wa−2 and (b−a−1) sets of three new vertices, namely, {v11, v21, v31}, {v12, v22, v32}, . . . , {v1(b−a−1), v2(b−a−1), v3(b−a−1)} for i = 1, 2, 3, with the paths P1 : u3, v11, v21, v31, u7, P2 : u3, v12, v22, v32, u7, . . . , Pb−a−1 : u3, v1(b−a−1), v2(b−a−1), v3(b−a−1), u7 such that vik is not adjacent to vij , j ̸= k and j, k = 1, 2, 3, . . . , b− a− 1 and joining each wi(1 ≤ i ≤ a− 2) with u3. The graph G is shown in Figure 2. Let S = {u1, u8, w1, w2, . . . , wa−2}. It is clear that this is an edge geodetic basis of G, so that ge(G) = a − 2 + 2 = a. Moreover, u2, u7, and u3 are dominated by u1, u8 and wi, respectively. Hence, we are left with u4, u5, u6, vij for i = 1, 2, 3 and 1 ≤ j ≤ b − a − 1 which are nondominated vertices. To get the minimum cardinality of edge geodetic dominating set, we need to choose u5, and v2j for (1 ≤ j ≤ b− a− 1). Therefore, γge(G) = ge(G) + (b− a− 1) + 1 = a+ b− a− 1 + 1 = b. C.J. Quije, R. Mariano, E. Ahmad / Eur. J. Pure Appl. Math, 18 (1) (2025), 5555 7 of 8 Figure 2: A graph G 4. Conclusion and Recommendation This study introduced and investigated the concept of edge geodetic dominating set S of the graph G. The authors primary focus has been on the following areas: deletion of independent edges of complete graph, the Kr-gluing of complete graphs, and result of comprehension. Researchers who are interested in this concept can further generate results in the various graph operations that include cartesian product and composition of graphs, among many others. Furthermore, they may explore and analyze the bounds in relation to other well-established parameters in graph theory. Acknowledgements The authors extend their sincere gratitude to the panel of reviewers for their insightful comments and recommendations, which significantly enhanced the quality of this paper. Additionally, the authors express their appreciation to Ateneo de Zamboanga University, Tangub City Global College, and Western Mindanao State University for supporting this research. References [1] A. Asdain, J. I. Salim, and R. G. Artes Jr. Geodetic bounds in graphs. International Journal of Mathematics and Computer Science, 18(4):767–771, 2023. [2] A. T. Castaneda, M. A. Medina, and L. Ruivivar. Notions of domination for some classes of graphs. DLSU Research Congress, 2016. [3] G. Chartrand, F. Harary, and P. Zhang. Geodetic sets in graphs. Discussioness Mathematicae Graph Theory, 20(1):129–138, 2000. C.J. Quije, R. Mariano, E. Ahmad / Eur. J. Pure Appl. Math, 18 (1) (2025), 5555 8 of 8 [4] H. Escuadro, R. Gera, A. Hansberg, N. Jafari Rad, and L. Volkmann. Geodetic domination in graphs. Journal of Combinatorial Mathematics and Combinatorial Computing, 77:89–101, 2011. [5] A. Gamorez and S. Canoy Jr. Monophonic eccentric domination numbers of graphs. European Journal of Pure and Applied Mathematics, 15(2):635–645, 2022. [6] A. Hansberg and L. Volkmann. On the geodetic and geodetic domination number of a graph. Discrete Mathematics, 310(15–16):2140–2146, 2010. [7] J. Harris, J. Hirst, and M. Mossinghoff. Combinatorics and Graph Theory. Springer Science + Business Media, Lawrence University, 2008. [8] R. Mariano and S. Canoy Jr. Edge geodetic cover in graphs. International Mathe- matical Forum, 4:2301–2310, 2009. [9] V. Samodivkin. On the edge geodetic and edge geodetic domination number of a graph. Communications in Combinatorics and Optimization, 5:41–54, 2020. [10] E. Sandueta and S. Canoy Jr. Weakly connected domination in graphs resulting from some graph operations. International Mathematical Forum, 6:1031–1035, 2011. [11] A. P. Santhakumaran. Comment on edge geodetic cover in graphs. Proyecciones Journal of Mathematics, 34:343–350, 2015. [12] A. P. Santhakumaran and J. John. Edge geodetic number of a graph. Journal of Discrete Mathematical Sciences and Cryptography, 10:415–432, 2007. [13] D. Stalin and J. John. Edge geodetic dominations in graphs. International Journal of Pure and Applied Mathematics, 116:31–40, 2017. [14] P. A. P. Sudhahar, A. Ajitha, and A. Subramanian. Edge geodetic domination number of a graph. International Journal of Mathematics and its Applications, 4:45–50, 2016. [15] A. Vijayan and N. Jaspin Beaula. Geodetic dominating sets and geodetic dominating polynomials of cycles. International Journal of Engineering Science and Computing, 6:3774–3779, 2016.