EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS 2025, Vol. 18, Issue 3, Article Number 6438 ISSN 1307-5543 – ejpam.com Published by New York Business Global Computing Metric and Connected Metric Dimension of Some Graphs Ashraf Elrokh1,∗, Eman S. Almotairi2, Hoda Mostafa3 1 Mathematics and Computer Science Department, Faculty of Science Menoufia University, Menoufia, Egypt 2 Department of Mathematics, College of Science, Qassim University, Buraydah 51452, Saudi Arabia 3 Department of Basic science, Giza Higher Institute of Engineering and Technology, Giza, Egypt Abstract. For a connected graph G = (V,E), a set B ⊆ V (G) is a resolving set if every vertex in G is uniquely identified by its distances to the vertices in B. A resolving set that induces a connected subgraph is called a connected resolving set. The minimum cardinality of such a set is the connected metric dimension, denoted cdim(G). In this paper, we compute the metric and connected metric dimensions for several classes of corona product graphs and propose an approximate algorithm to determine the connected metric dimension of arbitrary graphs. 2020 Mathematics Subject Classifications: 05C78, 05C15 Key Words and Phrases: Algebraic Graph, metric basis, resolving set, metric dimensions, Connected metric dimensions, Algorithm, Network security, Edge Computing 1. Introduction Let G be a connected graph and d (x, y) be the distance between the vertices x and y. A subset of vertices W = (w1, . . . , wk) is called a resolving set for G if for every two distinct vertices x, y ∈ V (G) , there is a vertex wi ∈ W such that d(x, [wi]) ̸= d(y, wi, ). The metric dimension dim(G) of G is the minimum cardinality of a resolving set for G. The concept of metric dimension was put forward by Slater [1], where it was expressed as locating sets, and later by Harary and Melter [2] called it as a metric dimension where the associate editor coordinating the review of this manuscript and approving it for pub- lication was Yilun Shang. the metric generators were termed as resolving sets. There are numerous metric dimension applications, such as identifying an intruder in a network, robotics navigation, chemistry, and pattern recognition or image processing; for further studies related to this invariant, some of the references are, see, for instance, [3–5]. Some ∗Corresponding author. DOI: https://doi.org/10.29020/nybg.ejpam.v18i3.6438 Email addresses: ashraf.hefnawy68@yahoo.com (Ashraf Elrokh) https://www.ejpam.com 1 Copyright: © 2025 The Author(s). (CC BY-NC 4.0) A. Elrokh, Eman S. Almotairi, H. Mostafa / Eur. J. Pure Appl. Math, 18 (3) (2025), 6438 2 of 18 of the recent studies on the metric dimension are in [6–8]. The metric dimension dim(G) of G is the minimum cardinality of a resolving set for G. Slater [9, 10] introduced the concept of a resolving set for a connected graph under the term locating set. He referred to a minimum resolving set as a reference set, and the cardinality of a minimum resolving set as the location number of a graph. Independently, Harary and Melter [11] studied these concepts under the term metric dimension. A resolving set S of G is called a connected resolving set of G if G[S] is connected, and the connected metric dimension of G, denoted by cdim(G), is the minimum cardinality of S over all connected resolving sets of G. For v ∈ V (G), we define the connected metric dimension at v of G, denoted by cdim(v), to be the minimum cardinality of a resolving set of G which contains v and induces a connected sub graph of G; then cdim(G) = minv ∈ V (G){cdimG(v)} for any vertex v ∈ V (G). Moreover, connected metric dimension theory is used by wireless communication networks, electrical networks, chemical structures, and commercial networks [12–28]. This paper is organized as follows: the metric and connected metric dimension introduced in Sect. 2 the theorems that determine the metric and connected metric dimension of some graphs along with examples in Section 3. In Sect. 4 an approximate algorithm which finds the minimum connected metric dimension Finally, conclusions are drawn in Sect. 5. Definition 1 [21–23, 29]: The corona G1 ⊙ G2 of two graphs G1 (with n1 vertices and m1 edges)and G2 (with n2 vertices and m2 edges) is defined as the graph obtained by taking one copy of G1 and n1 copies of G2, and then joining the ithvertex of G1with an edge to every vertex in the ith copy of G2. It follows from the definition of the corona that G1 ⊙ G2 has n1 + n1n2 vertices and m1n1m2 + n1n2 edges. As show in Figure 1. Figure 1. The corona product between two graphs G1 and G2. Definition 2 [12]: For a connected graph G = (V,E) , a set of vertices B ⊆ V (G) resolves G if every vertex of G is uniquely determined by its vector of distances to the vertices in B. Mathematically: r(v| B) = (d(v, x1), d(v, x2), ...., d(v, xk)) is unique for every v ∈ V (G). Definition 3 (Metric basis): The minimum resolving set is called the metric basis. Definition 4 (Metric dimension) [13]: The cardinality of the basis is called the metric dimension of G denoted by dim(G). As show in Figures 2, 3. A. Elrokh, Eman S. Almotairi, H. Mostafa / Eur. J. Pure Appl. Math, 18 (3) (2025), 6438 3 of 18 Figure 2. Metric dimension of P2 ⊙ C5. Figure 3. Metric dimension of C4 ⊙ C5. Definition 5 [11]: A metric basis B of G is connected if the sub graph induced by B is a nontrivial connected sub graph of G. The cardinality number of the connected metric basis is the connected metric dimension of G and is denoted cdim(G). As show in Figure 4. Figure 4. Connected metric dimension of C4 ⊙ C5. The remaining of this paper is organized as follows: the metric and connected metric dimension introduced in Sect. 2 the theorems that determine the metric and connected metric dimension of some graphs. with an example in Section 3. In Sect. 4 an approximate algorithm which finds the minimum connected metric dimension Finally, conclusions are drawn in Sect. 5. A. Elrokh, Eman S. Almotairi, H. Mostafa / Eur. J. Pure Appl. Math, 18 (3) (2025), 6438 4 of 18 2. Main result In this section, we prove the theorems that determine the metric and connected metric dimension of some graphs. Theorem 1: Let G be Pn ⊙ P3 graphs, then C.M.D (Pn ⊙ P3) equal 2n, n ≥ 1. Proof. Let Pn be the path graph with vertex set {v1, v2, . . . , vn} and edges vi ∼ vi+1 for 1 ≤ i < n. In the corona product Pn ⊙ P3, for each vertex vi of Pn, we attach a copy of P3 denoted by ui1, ui2, ui3 and connect each uij to vi , as show in Figure 5. Define the set R = {v1, v2, . . . , vn} ∪ {ui1 | 1 ≤ i ≤ n}. Clearly, |R| = 2n. We will show that R is a connected resolving set and that no smaller such set exists. (i) R is a resolving set: We must show that for any two distinct vertices x, y ∈ V (G), the distance vectors r(x|R) and r(y|R) are distinct. • For vertices in different P3 copies, the distances to the corresponding vi and ui1 in R distinguish them. • Within each P3 copy, the inclusion of ui1 and vi in R ensures that the other two vertices ui2, ui3 are distinguishable by their distances to ui1 and vi. • Vertices vi are all in R, so they are trivially distinguished. • Any vertex in Pn and any vertex in a P3 copy are distinguished by their distances to R. Figure 5. Pn ⊙ P3 graph. w (vi,R) =  {0, 1, 2, . . . , n− 1, 1, 2, 3, . . . , n} , i = 1 {1, 0, 1, . . . , n− 2, 2, 1, 2, . . . , n− 1} , i = 2 {2, 1, 0, 1, . . . , n− 3, 3, 2, 1, 2, . . . , n− 2} , i = 3 : : : {n− 2, n− 3, n− 4, . . . , 1, 2, , 3, n− 2, . . . , 2, 1, 2, 3} , i = n− 2 {n− 1, n− 2, n− 3, . . . , 2, 1, 2, 3, 2, 1, 2, . . . , 3, 2, 1, 2} , i = n− 1 {n, n− 1, n− 2, n− 3, . . . , 3, 2, 1, n, . . . , 3, 2, 1} .i = n A. Elrokh, Eman S. Almotairi, H. Mostafa / Eur. J. Pure Appl. Math, 18 (3) (2025), 6438 5 of 18 w (uij ,R) =  {1, 2, 3, . . . , n, j − 1, 3, 4, . . . , n, n+ 1} , i = 1 {2, 1, 2, . . . , n− 1, 3, j − 1, 3, 4, . . . , n− 1, n} , i = 2 {3, 2, 1, 2, . . . , n− 2, 4, 3, j − 1, 3, 4, . . . , n− 2, n− 1} , i = 3 : : : {n− 2, n− 3, n− 4, . . . , 2, 3, . . . , n− 1, n− 2, 4, 3, j − 1, 3, 4} , i = n− 2 {n− 1, n− 2, n− 3, . . . , n− 1, n, n− 1, . . . , 4, 3, j − 1, 3} , i = n− 1 {n, n− 1, n− 2, . . . , 1, n+ 1, n, . . . , 4, 3, j − 1} .i = n (ii) R is connected: The subgraph induced by {v1, . . . , vn} is a path and hence connected. Each ui1 is adjacent to vi, so the full induced subgraph on R is connected. (iii) Minimality: Suppose there exists a connected resolving set R′ with |R′| < 2n. Then at least one vi or ui1 is missing from R′. If vi /∈ R′, then ui1 may be disconnected from the rest of R′, violating connectivity. If ui1 /∈ R′, then ui2 and ui3 may not be distinguishable. Thus, removing any vertex from R breaks either the resolving property or connectivity. Therefore, R is a minimum connected resolving set, and cdim(Pn ⊙ P3) = 2n. Theorem 2: Let G be Pn ⊙ C3 graphs, then the connected metric dimension of Pn ⊙ C3 equal to 3n, n ≥ 1. Proof. Let Pn be a path graph with vertices v1, v2, . . . , vn. For each vertex vi in Pn, attach a copy of the cycle C3 with vertices ui1, ui2, ui3, and connect each uij to vi, as show in Figure 6. The resulting graph G = Pn ⊙ C3 has n central vertices and 3n peripheral vertices, totaling 4n vertices. We define the set R = {v1, v2, . . . , vn} ∪ {ui1, ui2 | 1 ≤ i ≤ n}, which includes all n central vertices and two vertices from each C3 copy. Thus, |R| = n+ 2n = 3n. (i) R is a resolving set. Consider any two distinct vertices x, y ∈ V (G). We analyze the following cases: • Case 1: x and y belong to different C3 copies. Since each vi is in R, and each uij is connected to vi, the distances to vi and the included ui1, ui2 uniquely identify vertices in each C3 copy. • Case 2: x and y belong to the same C3 copy. The inclusion of two vertices from each C3 ensures that all three vertices in the cycle are distinguishable by their distances to the two included vertices. • Case 3: One of x or y is a central vertex vi, and the other is a peripheral vertex uij . Since vi is in R and ui1, ui2 are also in R, the distance vectors to R will differ. A. Elrokh, Eman S. Almotairi, H. Mostafa / Eur. J. Pure Appl. Math, 18 (3) (2025), 6438 6 of 18 • Case 4: x and y are distinct central vertices. Since all vi are in R, they are trivially resolved. Figure 6. Pn ⊙ C3 graph. w (vi,R) =  {0, 1, 2, . . . , n− 1, 1, 1, 2, 2, 3, 3, . . . , n, n} , i = 1 {1, 0, 1, . . . , n− 2, 2, 2, 1, 1, 2, 2 . . . , n− 1, n− 1} , i = 2 {2, 1, 0, 1, . . . , n− 3, 3, 3, 2, 2, 1, 1, . . . , n− 2, n− 2} , i = 3 : : : : : {n− 1, n− 2, n− 3, . . . , 0, n, n.n− 1, n− 1, . . . , 1, 1} .i = n w (uij ,R) =  {1, 2, 3, . . . , n, n, j − 1, j, 3, 3, 4, 4, . . . , n, n, n+ 1, n+ 1} , i = 1, j = 1 {1, 2, 3, . . . , n, n, j − 1, j − 2, 3, 3, 4, 4, . . . , n, n, n+ 1, n+ 1} , i = 1, j = 2 {1, 2, 3, . . . , n, n, j − 2, j − 2, 3, 3, 4, 4, . . . , n, n, n+ 1, n+ 1} , i = 1, j = 3 {2, 1, 2, 3, 4 . . . , n− 1, 3, 3, j − 1, j, 3, 3, 4, 4, . . . , n, n} , i = 2, j = 1 {2, 1, 2, 3, 4 . . . , n− 1, 3, 3, j − 1, j − 2, 3, 3, 4, 4, . . . , n, n} , i = 2, j = 2 {2, 1, 2, 3, 4 . . . , n− 1, 3, 3, j − 2, j − 2, 3, 3, 4, 4, . . . , n, n} , i = 2, j = 3 : : : {n− 1, n− 2, . . . ., 1, n+ 1, n+ 1, n, n, n− 1, n− 1, j − 1, j} , i = n , j = 1 {n− 1, n− 2, . . . ., 1, n+ 1, n+ 1, n, n, n− 1, n− 1, j − 1, j − 2} , i = n , j = 2 {n− 1, n− 2, . . . ., 1, n+ 1, n+ 1, n, n, n− 1, n− 1, j − 2, j − 2} , i = n , j = 3 Hence, R is a resolving set. (ii) R induces a connected subgraph. The subgraph induced by {v1, . . . , vn} is a path and hence connected. Each ui1 and ui2 is adjacent to vi, so the full induced subgraph is connected. (iii) R is minimal. A. Elrokh, Eman S. Almotairi, H. Mostafa / Eur. J. Pure Appl. Math, 18 (3) (2025), 6438 7 of 18 Suppose there exists a connected resolving set R′ with |R′| < 3n. Then for some i, at most one of ui1, ui2 is in R′. But in a C3 cycle, at least two vertices are needed to resolve all three vertices. Removing any vi would disconnect the corresponding C3 copy from the rest of the graph. Thus, R′ cannot be both resolving and connected. Therefore, R is a minimal connected resolving set of size 3n. Theorem 3: The connected metric dimension of Cn ⊙ P3 equal to 2n, if n ≥ 3. Proof. The corona product Cn ⊙ P3 is formed by taking a cycle Cn with vertices v1, v2, . . . , vn and attaching to each vi a copy of P3 with vertices ui1, ui2, ui3, where each uij is connected to vi , as show in Figure 7. We construct a set R consisting of: R = {v1, v2, . . . , vn} ∪ {ui1 | 1 ≤ i ≤ n} Thus, |R| = 2n. Resolving Property: • Each vi is in R, so any pair of vi, vj is trivially resolved. • For each P3 copy, the inclusion of ui1 and vi ensures that the other two vertices ui2, ui3 are uniquely identified by their distances to ui1 and vi. • Vertices from different P3 copies are distinguished by their distances to the corre- sponding vi and ui1. Figure 7. The Cn ⊙ P3 graph. w (vi,R) =  {0, 1, 2, . . . , 1, 1, 2, . . . , 2} , i = 1 {1, 0, 1, . . . , 2, 2, 1, 2, . . . , 2} , i = 2 {2, 1, 0, 1, . . . , 2, 3, 2, 1, . . . , 3} , i = 3 : : : : {1, 2, 3, . . . , 0, 2, 3, n− 2, . . . , 2, 1} .i = n A. Elrokh, Eman S. Almotairi, H. Mostafa / Eur. J. Pure Appl. Math, 18 (3) (2025), 6438 8 of 18 w (uij ,R) =  {1, 2, 3, . . . , 2, j − 1, 3, 4, . . . , 3} , i = 1 {2, 1, 2, . . . , 3, 3, j − 1, 3, . . . , n− 2, n− 1, 4} , i = 2 {3, 2, 1, 2, . . . , n− 2, 4, 3, j − 1, 3, 4, . . . , n− 2, n− 1} , i = 3 : : : : {1, 2, 3, 4 . . . , 1, 3, 4, . . . , 4, 3, j − 1} .i = n Connectivity: The subgraph induced by R includes the cycle Cn (which is connected) and each ui1 is connected to vi, forming a connected tree-like structure rooted at the cycle. Minimality: Suppose a smaller connected resolving set R′ exists with |R′| < 2n. Then at least one vi or ui1 is missing. If vi /∈ R′, then ui1 may become disconnected or fail to resolve its P3 copy. If ui1 /∈ R′, then ui2, ui3 may not be distinguishable. Hence, R is minimal. Therefore, cdim(Cn ⊙ P3) = 2n. Theorem 4: If n ≥ 3, then connected metric dimension of Cn ⊙ C3 graphs are equal 3n. Proof. The corona product Cn ⊙ C3 is formed by taking a cycle Cn with vertices v1, v2, . . . , vn and attaching to each vi a copy of C3 with vertices ui1, ui2, ui3, where each uij is connected to vi , as show in Figure 8. We construct a set R consisting of: R = {v1, v2, . . . , vn} ∪ {ui1, ui2 | 1 ≤ i ≤ n} Thus, |R| = 3n. Resolving Property: • Each vi is in R, so all cycle vertices are resolved. • Including two vertices from each C3 copy ensures that all three vertices in the triangle are distinguishable. • Vertices from different C3 copies are resolved by their distances to the corresponding vi, ui1, and ui2. A. Elrokh, Eman S. Almotairi, H. Mostafa / Eur. J. Pure Appl. Math, 18 (3) (2025), 6438 9 of 18 Figure 8. The Cn ⊙ C3 graph. w (vi,R) =  {0, 1, 2, . . . , n− 1, 1, 1, 2, 2, 3, 3, . . . , n, n} , i = 1 {1, 0, 1, . . . , n− 2, 2, 2, 1, 1, 2, 2 . . . , n− 1, n− 1} , i = 2 {2, 1, 0, 1, . . . , n− 3, 3, 3, 2, 2, 1, 1, . . . , n− 2, n− 2} , i = 3 : : : : {n− 1, n− 2, n− 3, . . . , 0, n, n.n− 1, n− 1, . . . , 1, 1} .i = n w (uij ,R) =  {1, 2, 3, . . . , n, 0, 1, . . . , n, n, n+ 1, n+ 1} , i = 1, j = 1 {1, 2, 3, . . . , n, 1, 0, . . . , n, n, n+ 1, n+ 1} , i = 1, j = 2 {1, 2, 3, . . . , n, 1, 1, . . . , n, n, n+ 1, n+ 1} , i = 1, j = 3 {2, 1, 2, 3 . . . , n− 1, 3, 3, j − 1, j, 3, 3, 4, 4, . . . , n, n} , i = 2, j = 1 {2, 1, 2, 3 . . . , n− 1, 3, 3, j − 1, j − 2, 3, 3, 4, 4, . . . , n, n} , i = 2, j = 2 {2, 1, 2, 3 . . . , n− 1, 3, 3, j − 2, j − 2, 3, 3, 4, 4, . . . , n, n} , i = 2, j = 3 : : : {n, n− 1, . . . ., 1, n+ 1, n+ 1, n, n, n− 1, n− 1, . . . ., j − 1, j} , i = n , j = 1 {n, n− 1, . . . ., 1, n+ 1, n+ 1, n, n, n− 1, n− 1, . . . ., j − 1, j − 2} , i = n , j = 2 {n, n− 1, . . . ., 1, n+ 1, n+ 1, n, n, n− 1, n− 1, . . . ., j − 2, j − 2} , i = n , j = 3 Connectivity: The subgraph induced by R includes the cycle Cn and two vertices from each triangle connected to vi. Since each ui1, ui2 is adjacent to vi, the induced subgraph is connected. Minimality: Suppose a smaller connected resolving set R′ exists with |R′| < 3n. Then at least one vi, ui1, or ui2 is missing. Omitting any of these may cause failure to resolve the triangle or disconnect the induced subgraph. Hence, R is minimal. Therefore, cdim(Cn ⊙ C3) = 3n. In the following theorems, we study and investigate the metric dimension of Pn ⊙ P3, Cn ⊙ P3, Pn ⊙ C3, Cn ⊙ C3 and Kim,n. Theorem 5: Let G be Pn ⊙ P3 graphs, then M.D (Pn ⊙ P3) = n. Proof. Label the vertices of Pn as v1, v2, . . . , vn. For each vi, attach a copy of P3 with vertices ui1, ui2, ui3, where each uij is adjacent to vi, as show in Figure 9. Let R = {ui1 | 1 ≤ i ≤ n}. We claim that R is a resolving set. Each vi is uniquely identified by its distance to ui1 (which is 1), and to all other uj1 (which are at least 2). Similarly, within each P3 copy, the vertices ui2 and ui3 are distinguishable by their distances to ui1 (which are 2), while ui1 is in R. A. Elrokh, Eman S. Almotairi, H. Mostafa / Eur. J. Pure Appl. Math, 18 (3) (2025), 6438 10 of 18 Figure 9. Pn ⊙ P3 graph. w (vi,R) =  {1, 2, 3, . . . , n} , i = 1 {2, 1, 2, . . . , n− 1} , i = 2 {3, 2, 1, 2, . . . , n− 2} , i = 3 : : : {n− 2, . . . , 2, 1, 2, 3} , i = n− 2 {n− 1, . . . , 2, 1, 2, 3} , i = n− 1 {n, . . . , 3, 2, 1} .i = n w (uij ,R) =  {j − 1, 3, 4, . . . , n, n+ 1} , i = 1 {3, j − 1, 3, 4, . . . , n− 1, n} , i = 2 {4, 3, j − 1, 3, 4, . . . , n− 2, n− 1} , i = 3 : : : {n− 1, n− 2, 4, 3, j − 1, 3, 4} , i = n− 2 {n, n− 1, . . . , 4, 3, j − 1, 3} , i = n− 1 {n+ 1, n, . . . , 4, 3, j − 1} .i = n Thus, all vertices are uniquely identified by their distance vectors to R, and |R| = n. To show minimality, note that if any ui1 is removed from R, then the vertices in the i-th P3 copy are no longer distinguishable. Hence, dim(G) = n. Theorem 6: Let G be Cn ⊙ P3 graph, then M.D (Cn ⊙ P3) = n, n ≥ 3. Proof. Label the cycle Cn as v1, v2, . . . , vn in cyclic order. For each vi, attach a copy of P3 with vertices ui1, ui2, ui3, each adjacent to vi, as show in Figure 10. Let R = {ui1 | 1 ≤ i ≤ n}. We claim that R is a resolving set. A. Elrokh, Eman S. Almotairi, H. Mostafa / Eur. J. Pure Appl. Math, 18 (3) (2025), 6438 11 of 18 Figure 10. The Cn ⊙ P3 graph. w (vi,R) =  {1, 2, . . . , 2} , i = 1 {2, 1, 2, . . . , 2} , i = 2 {3, 2, 1, . . . , 3} , i = 3 : : : {2, 3, n− 2, . . . , 2, 1} .i = n w (uij ,R) =  {j − 1, 3, 4, . . . , 3} , i = 1 {3, j − 1, 3, . . . , n− 2, n− 1, 4} , i = 2 {4, 3, j − 1, 3, 4, . . . , n− 2, n− 1} , i = 3 : : : {3, 4, . . . , 4, 3, j − 1} .i = n Each vi is uniquely identified by its distance to ui1 (which is 1), and to other uj1 (which vary due to the cycle structure). Each uij in the i-th P3 copy is distinguishable by its distance to ui1. If any ui1 is removed, then the corresponding P3 copy cannot be resolved. Hence, R is minimal and dim(G) = n. Theorem 7: Let G be Pn ⊙ C3 graph, then M.D (Pn ⊙ C3) = 2n, n ≥ 1. Proof. Label the path Pn as v1, v2, . . . , vn. For each vi, attach a copy of C3 with vertices ui1, ui2, ui3 forming a triangle, and connect each to vi, as show in Figure 11. Let R = {ui1, ui2 | 1 ≤ i ≤ n}. We claim that R is a resolving set. Figure 11. The Pn ⊙ C3 graph. A. Elrokh, Eman S. Almotairi, H. Mostafa / Eur. J. Pure Appl. Math, 18 (3) (2025), 6438 12 of 18 w (vi,R) =  {1, 1, 2, 2, 3, 3, . . . , n, n} , i = 1 {2, 2, 1, 1, 2, 2 . . . , n− 1, n− 1} , i = 2 {3, 3, 2, 2, 1, 1, . . . , n− 2, n− 2} , i = 3 : : : {n, n.n− 1, n− 1, . . . , 1, 1} .i = n w (uij ,R) =  {j − 1, j, 3, 3, 4, 4, . . . , n, n, n+ 1, n+ 1} , i = 1, j = 1 {j − 1, j − 2, 3, 3, 4, 4, . . . , n, n, n+ 1, n+ 1} , i = 1, j = 2 {j − 2, j − 2, 3, 3, 4, 4, . . . , n, n, n+ 1, n+ 1} , i = 1, j = 3 {3, 3, j − 1, j, 3, 3, 4, 4, . . . , n, n} , i = 2, j = 1 {3, 3, j − 1, j − 2, 3, 3, 4, 4, . . . , n, n} , i = 2, j = 2 {3, 3, j − 2, j − 2, 3, 3, 4, 4, . . . , n, n} , i = 2, j = 3 : : : {n+ 1, n+ 1, n, n, n− 1, n− 1, j − 1, j} , i = n , j = 1 {n+ 1, n+ 1, n, n, n− 1, n− 1, j − 1, j − 2} , i = n , j = 2 {n+ 1, n+ 1, n, n, n− 1, n− 1, j − 2, j − 2} , i = n , j = 3 Each vi is uniquely identified by its distances to ui1 and ui2 (both 1), and to other ujk (which are at least 2). Each ui3 is distinguishable from ui1 and ui2 by its distances to them (1 or 2). Removing any ui1 or ui2 would make the i-th C3 copy unresolved. Hence, R is minimal and dim(G) = 2n. Theorem 8: Let G be Cn ⊙ C3 graph, then M.D (Cn ⊙ C3) = 2n, n ≥ 3. Proof. Label the cycle Cn as v1, v2, . . . , vn. For each vi, attach a copy of C3 with vertices ui1, ui2, ui3 forming a triangle, and connect each to vi, as show in Figure 12. Let R = {ui1, ui2 | 1 ≤ i ≤ n}. We claim that R is a resolving set. Figure 12. The Cn ⊙ C3 graph. A. Elrokh, Eman S. Almotairi, H. Mostafa / Eur. J. Pure Appl. Math, 18 (3) (2025), 6438 13 of 18 w (vi,R) =  {1, 1, 2, 2, 3, 3, . . . , n, n} , i = 1 {2, 2, 1, 1, 2, 2 . . . , n− 1, n− 1} , i = 2 {3, 3, 2, 2, 1, 1, . . . , n− 2, n− 2} , i = 3 : : : : : {n, n, n− 1, n− 1, . . . , 1, 1} .i = n w (uij ,R) =  {0, 1, . . . , n, n, n+ 1, n+ 1} , i = 1, j = 1 {1, 0, . . . , n, n, n+ 1, n+ 1} , i = 1, j = 2 {1, 1, . . . , n, n, n+ 1, n+ 1} , i = 1, j = 3 {3, 3, j − 1, j, 3, 3, 4, 4, . . . , n, n} , i = 2, j = 1 {3, 3, j − 1, j − 2, 3, 3, 4, 4, . . . , n, n} , i = 2, j = 2 {3, 3, j − 2, j − 2, 3, 3, 4, 4, . . . , n, n} , i = 2, j = 3 : : : {n+ 1, n+ 1, n, n, n− 1, n− 1, . . . ., j − 1, j} , i = n , j = 1 {n+ 1, n+ 1, n, n, n− 1, n− 1, . . . ., j − 1, j − 2} , i = n , j = 2 {n+ 1, n+ 1, n, n, n− 1, n− 1, . . . ., j − 2, j − 2} , i = n , j = 3 Each vi is uniquely identified by its distances to ui1 and ui2 (both 1), and to other ujk (which vary due to the cycle). Each ui3 is distinguishable from ui1 and ui2 by its distances to them. Removing any ui1 or ui2 would make the i-th C3 copy unresolved. Hence, R is minimal and dim(G) = 2n. Theorem 9: Let G be Kim,n graph, then M.D. (Kim,n) = 2, if m is odd. Proof. We labelling Kim,n, as show in Figure 13. It is clear that the number of vertices is n+m. Let R = {v1,vn+2} be any resolving set of Kim,n. Figure 13. The Kim,n graph. A. Elrokh, Eman S. Almotairi, H. Mostafa / Eur. J. Pure Appl. Math, 18 (3) (2025), 6438 14 of 18 Being For ( i = 1; i ≤ 2; i = i+ 1) do r (vi, R) = {i− 1, n} End For (i = 3; i ≤ n+m; i = i+ 1) do r (vi, R) = {i− 2, |n+ 2− i|} End We aim to show that the metric dimension of G is 2. That is, there exists a resolving set R ⊆ V (G) with |R| = 2 such that for every pair of distinct vertices x, y ∈ V (G), the distance vectors r(x|R) and r(y|R) are distinct. Let us choose R = {u1, v1}, where u1 ∈ U and v1 ∈ V . We will show that R resolves all vertices in G. Case 1: x, y ∈ U , x ̸= y. Then d(x, u1) = 0 if x = u1, and 2 otherwise (since x and u1 are in the same partite set and not adjacent, but both are adjacent to all vertices in V ). Also, d(x, v1) = 1 for all x ∈ U since each x is adjacent to v1. Thus, the distance vectors differ at the first coordinate if x = u1, and otherwise they differ due to symmetry and the odd cardinality of U . Case 2: x, y ∈ V , x ̸= y. Similarly, d(x, v1) = 0 if x = v1, and 2 otherwise. Also, d(x, u1) = 1 for all x ∈ V . Hence, the distance vectors differ at the second coordinate if x = v1, and otherwise they are distinguishable. Case 3: x ∈ U , y ∈ V . Then d(x, u1) ∈ {0, 2} and d(y, u1) = 1, so the first coordinates differ. Hence, r(x|R) ̸= r(y|R). Therefore, R = {u1, v1} is a resolving set, and dim(G) ≤ 2. To prove minimality, suppose there exists a resolving set R′ with |R′| = 1. Then all vertices in one partite set are equidistant from the single vertex in R′, and hence cannot be distinguished. Therefore, no single vertex can resolve G, and dim(G) ≥ 2. Thus, dim(G) = 2. 3. Algorithm for Connected Metric Dimension In this section, we propose an algorithm that determines a connected Metric Dimension for an arbitrary graph G. this algorithm provides a basic framework for computing the connected metric dimension. For more complex graphs, heuristic or metanephritic ap- proaches like Genetic Algorithms or Binary Equilibrium Optimization Algorithm can be used to find optimal or near-optimal solutions efficiently. Algorithm: Connected Metric Dimension A. Elrokh, Eman S. Almotairi, H. Mostafa / Eur. J. Pure Appl. Math, 18 (3) (2025), 6438 15 of 18 Input: A connected graph G = (V , E) Output: A connected resolving set (S) with the smallest possible size Initialization: Let (S) be an empty set. Let (U) be the set of all vertices in (V ). Step 1: Select Initial Vertex: Choose an arbitrary vertex (v ∈ V ) and add it to (S). Remove (v) from (U). Step 2: Iterative Selection: While (U) is not empty: For each vertex (u ∈ U): Calculate the distance from u to all vertices in S. Step 3: Select the vertex (u ∈ U) that maximizes the number of vertices in U that can be uniquely identified by their distances to the vertices in (S). Add (u) to (S). Remove (u) from (U). Step 4: Ensure Connectivity: Check if the sub graph induced by (S) is connected. If not, add the necessary vertices from (V⧹S) to (S) to make it connected. Step 5: Optimization: Attempt to remove any redundant vertices from (S) while maintaining its properties as a connected resolving set. Step 6: Output: Return the set (S). Example: Path with 4 Vertices and One Triangle Let G be a path P4 with vertices v1 − v2 − v3 − v4 and a triangle u1, u2, u3 attached to v2. • Step 1: Choose v2 as initial vertex ⇒ S = {v2} • Step 2: Add v1 (distinguishes v1 and v3) ⇒ S = {v2, v1} • Step 3: Add u1 (distinguishes triangle vertices) ⇒ S = {v2, v1, u1} • Step 4: Ensure connectivity: v2 connects v1 and u1 ⇒ connected • Step 5: Check redundancy: all vertices resolved, S is minimal Correctness The algorithm ensures that: A. Elrokh, Eman S. Almotairi, H. Mostafa / Eur. J. Pure Appl. Math, 18 (3) (2025), 6438 16 of 18 • Each vertex is uniquely identified by its distance vector to S • The induced subgraph G[S] is connected Completeness The algorithm terminates when all vertices are resolved and S is connected. It guar- antees a valid connected resolving set. Time Complexity Let n = |V |, m = |E|: • Distance computation: O(n2) using BFS for each vertex • Selection loop: O(n2) comparisons • Connectivity check: O(n+m) • Redundancy check: O(n2) Total Time Complexity: O(n2) for sparse graphs 4. CONCLUSION We introduced metric and connected metric dimension of Pn ⊙ C3, Pn ⊙ P3, Cn ⊙ C3and Cn ⊙ P3. Graph Metric Dimension (dim) Connected Metric Dimension (cdim) Pn ⊙ P3 n 2n Pn ⊙ C3 2n 3n Cn ⊙ P3 n 2n Cn ⊙ C3 2n 3n Kim,n (m odd) 2 – Table 1: Summary of Metric and Connected Metric Dimensions for Various Graphs In the future, we will apply all of this proofs for another graphs. The third contribution is that proposing a new approximate algorithm which finds a minimum connected metric dimension Acknowledgements The Researchers would like to thank the Deanship of Graduate Studies and Scientific Research at Qassim University for financial support (QU-APC-2025). A. Elrokh, Eman S. Almotairi, H. Mostafa / Eur. J. Pure Appl. Math, 18 (3) (2025), 6438 17 of 18 Data Availability Statement All data generated or analyzed during this study are included in this published article. References [1] P. J. Slater. Leaves of trees. Congressus Numerantium, 14:549–559, 1975. In Proc. 6th Southeastern Conf. Combinatorics, Graph Theory, Comput., The Netherlands. [2] F. Harary and R. A. Melter. On the metric dimension of a graph. ARS Combinatoria, 2:191–195, 1976. [3] G. Chartrand, L. Eroh, M. A. Johnson, and O. R. Oellermann. Resolvability in graphs and the metric dimension of a graph. Discrete Applied Mathematics, 105(1-3):99–113, 2000. [4] G. Chartrand, C. Poisson, and P. Zhang. Resolvability and the upper dimension of graphs. Computers and Mathematics with Applications, 39(12):19–28, 2000. [5] S. Khuller, B. Raghavachari, and A. Rosenfeld. Landmarks in graphs. Discrete Applied Mathematics, 70(3):217–229, 1996. [6] M. Imran, M. K. Siddiqui, and R. Naeem. On the metric dimension of generalized petersen multigraphs. IEEE Access, 6:74328–74338, 2018. [7] J.-B. Liu, M. F. Nadeem, H. M. A. Siddiqui, and W. Nazir. Computing metric dimension of certain families of toeplitz graphs. IEEE Access, 7:126734–126741, 2019. [8] F. S. Raj and A. George. On the metric dimension of hdn 3 and phdn 3. In Proceedings of the IEEE International Conference on Power, Control, Signals and Instrumenta- tion Engineering (ICPCSI), pages 1333–1336, September 2017. [9] J. Currie and O. R. Oellermann. The metric dimension and metric independence of a graph. Journal of Combinatorial Mathematics and Combinatorial Computing, 39:157–167, 2001. [10] P. J. Slater. Leaves of trees. Congressus Numerantium, 14:549–559, 1975. [11] P. J. Slater. Dominating and reference sets in graphs. Journal of Mathematical and Physical Sciences, 22:445–455, 1988. [12] J. W. Essam and M. E. Fisher. Some basic definitions in graph theory. Reviews of Modern Physics, 42(2):271, 1970. [13] D. L. Boutin. Determining sets, resolving sets, and the exchange property. Graphs and Combinatorics, 25(6):789–806, 2009. [14] L. Eroh, C. X. Kang, and E. Yi. The connected metric dimension at a vertex of a graph. Theoretical Computer Science, 806:53–69, 2020. [15] L. Susilowati, I. Sa’adah, R. Z. Fauziyyah, and A. Erfanian. The dominant metric dimension of graphs. Heliyon, 6(3):e03633, 2020. [16] A. M. Bibi. Split and non split two domination number of a graph. International Journal of Advanced Research in Computer Science, 11(4):13–17, 2020. [17] J. Mohamad and H. Rara. Strong resolving hop domination in graphs. European Journal of Pure and Applied Mathematics, 16(1):131–143, 2023. [18] S. Nada, A. Elrokh, and Atef Abd El-hay. On signed product cordial of cone graph A. Elrokh, Eman S. Almotairi, H. Mostafa / Eur. J. Pure Appl. Math, 18 (3) (2025), 6438 18 of 18 and its second power. Turkish Journal of Computer and Mathematics Education (TURCOMAT), 13(3):597–606, 2022. [19] O. Favaron, H. Karami, R. Khoeilar, and S. M. Sheikholeslami. On the roman dom- ination number of a graph. Discrete Mathematics, 309(10):3447–3451, 2009. [20] A. Elrokh, Y. Elmshtaye, and Atef Abd El-hay. The cordiality of cone and lemniscate graphs. Applied Mathematics & Information Sciences, 16:1027–1034, 2022. [21] A. Abd El-hay and A. Rabie. Signed product cordial labeling of corona product between paths and second power of fan graphs. Italian Journal of Pure and Applied Mathematics, 48:287–294, 2022. [22] Ashraf Elrokh, Mohammed M. Ali Al-Shamiri, and Atef Abd El-hay. A novel problem for solving permuted cordial labeling of graphs. Symmetry, 15(4):825, 2023. [23] Atef Abd El-hay and A. Elrokh. Total cordial labeling of corona product of paths and second power of fan graph. Turkish Journal of Computer and Mathematics Education (TURCOMAT), 13(3):681–690, 2022. [24] Ashraf Elrokh, Mohammed M. Ali Al-Shamiri, and Atef Abd El-hay. A novel radio geometric mean algorithm for a graph. Symmetry, 15(3):570, 2023. [25] A. Abd El-hay, Y. Elmshtaye, and A. Elrokh. Solving signed product cordial labeling of corona products of paths and the third power of lemniscate graphs. Turkish Journal of Computer and Mathematics Education (TURCOMAT), 14(2):806–823, 2023. [26] K. A. Alsatami, Y. Algrawani, and A. Abd El-hay. A novel problem and algorithm for solving permuted cordial labeling of corona product between two graphs. Mathe- matical Models in Engineering, 11(1):1–11, 2025. [27] Atef Abd El-hay, Khalid A. Alsatami, Ashraf Elrokh, and Aya Rabie. Cordial labeling of corona product of paths and fourth order of lemniscate graphs. European Journal of Pure and Applied Mathematics, 18(1):5470, 2025. [28] Atef Abd El-hay, Khalid A. Alsatami, and Ashraf Elrokh. A novel problem and algorithm for solving cordial labeling of some fifth power of graphs. European Journal of Pure and Applied Mathematics, 18(1):5812, 2025. [29] Y. Elmshtaye, A. Elrokh, and A. Abd El-hay. Total cordial for the corona product of paths and the third power of double fans-generalized fans. Advances and Applications in Discrete Mathematics, 42(4):303–334, 2025.