# On Resolvability Parameters of Some Wheel-Related Graphs

Authors: Bin Yang; Muhammad Rafiullah; Hafiz Muhammad Afzal Siddiqui; Sarfraz Ahmad
Journal: Journal of Chemistry
 (2019)

---

## Abstract

LetG=V,E be a simple connected graph, w∈V be a vertex, and e=uv∈E be an edge. The distance between the vertex w and edge e is given by de,w=mindw,u,dw,v, A vertex w distinguishes two edges e1, e2∈E if dw,e1≠dw,e2. A set S is said to be resolving if every pair of edges of G is distinguished by some vertices of S. A resolving set with minimum cardinality is the basis for G, and this cardinality is the edge metric dimension of G, denoted by edimG. It has already been proved that the edge metric dimension is an NP-hard problem. The main objective of this article is to study the edge metric dimension of some families of wheel-related graphs and prove that these families have unbounded edge metric dimension. Moreover, the results are compared with the metric dimension of these graphs.


---

## Body

## 1. Introduction and Preliminary

The molecular structure of a chemical compound is known as molecular graph (or chemical graph). There are different structures of chemical compounds, and every structure correlated with many chemical properties, and these properties can be calculated through some specific mathematical formulas. Graph theory helps us to study and analyze these dense structures in detail. In graph theory, we consider every atom as a vertex and covalent bound between atoms as an edge. Agraph G consists of a set of objects VG=v1,v2,v3,…,vn called vertices, set of connections between vertices called edges EG=e1,e2,e3,…,em, and graph G is usually denoted as G=VG,EG. The number of vertices in G denoted by n=VG is often called the order of G, while the number of edges is known as size of G and denoted by m=EG. The concept of metric dimension was introduced by Slater in 1975 [1], and this concept independently was elaborated for graphs by Harary and Melter in 1976 [2]. After these two papers, lot of research papers have been published related to its theoretical properties and applications. The theoretical studies on metric dimension are highly contributed by several authors like, for instance, independent resolving sets [3], resolving dominating sets [4], strong resolving sets [5], local resolving sets [6], k-metric generators [7, 8], simultaneous metric generators [9], resolving partitions [10], strong resolving partitions [11], and k-antiresolving sets [12]. The metric dimension has many applications in the digital world and in mathematical chemistry such as network verification [13], robot navigation, image processing and pattern recognition [14], mastermind game [15], chemistry [16, 17, 18], and pharmaceutical chemistry [18].IfG is a simple connected graph and u and v are any two vertices of G, then the distance du,v is the length of a shortest path between u and v. Let S=s1,s2,s3,…,sk be an ordered set of vertices of G and let v be a vertex of G. The representation rvS of v with respect to S is the ordered k-tuple dv,s1,dv,s2,dv,s3,…,dv,sk. If dx,v≠dy,v, then we shall say that vertex v distinguishes two vertices x and y. If distinct vertices of G have distinct representations with respect to S, then S is called a resolving set for G. A resolving set of minimum cardinality is called a basis for G and the cardinality is known as metric dimension of G, and it is denoted as dimG.LetS be a set of vertices of a simple connected graph G. Then, S is called an edge metric generator for G if every two edges of G are distinguished by some vertices of S. The minimum cardinality of S is called the edge metric dimension, and it is denoted by edimG. For an ordered set of vertices S=s1,s2,…,sk of a graph G and any edge e in G, we refer to the k-vector (ordered k-tuple) reS=de,s1,de,s2,…de,sk as the edge metric representation of e with respect to S. The set S is an edge metric generator for G if and only if for every pair of different edges e1, e2 of G, re1S≠re2∣S.Letℱ=Gnn≥1 be a family of connected graphs Gn of order φn for which limφnn⟶∞=∞. If there exists a constant C>0 such that edimGn≤C for every n≥1, then we shall say that ℱ has a bounded edge metric dimension, otherwise ℱ has unbounded edge metric dimension. Moreover, if edimGn=C, ∀n≥1, then ℱ has a constant edge metric dimension.There is a controversy in the definition of edge resolving set and edge metric dimension. In the literature, another version of edge metric dimension exists, which is based on the distance between edges, denoted asdf,g. This version of edge metric dimension follows the following steps.Step 1. Convert a graph G into a line graph LG.Step 2. Find metric dimension, dimLG of line graph LG.According to the above steps,dimLG=edimG, for reference see [19]. But in our case, the distance is based on vertex to edge, dv,e, as defined by Kelenc et al. [20].In 1979, Garey and Johnson [21] pointed out that the finding of the metric dimension of a graph is an NP-hard problem. In 1994, Khuller et al. [22] also showed by another construction that the metric dimension of a graph is an NP-hard problem.Recently, Kelenc et al. [20] have introduced the notion of edge metric dimension of graph, denoted by edimG, and they presented some results relating the notions of metric dimension and edge metric dimension for some families of graph such as for path Pn: edimPn=dimPn=1 where n≥2, for cycle Cn: edimCn=dimCn=2, for complete graph Kn: edimKn=dimKn=n−1, where n≥2, for complete bipartite graph Kr,t: edimKr,t=dimKr,t=r+t−2, where r,t≥2, for tree Tn which is not a path: edimT=dimT=∑v∈V,Lv>1Lv−1, for grid graph G=Pr□Pt (where r≥t≥2): edimG=dimG=2, for wheel graph (G=S1,n): edimG>dimG, and for the grid graph G=Cr□Ct: edimCr□Ct<dimCr□Ct. They also proved that the edge metric dimension is an NP-hard problem. Moreover, they have raised many open problems related to edge metric dimension. Furthermore, in 2019, Zubrilina has classified some graphs on the same topic which has the edimG=V−1 in her paper [23]. Recently, in 2019, Rafiullah et al. studied the edge metric dimensions of wheel-related convex polytopes in [24] and characterized these graphs.This paper is based on the question raised in [20] to characterize the families of graphs which observe one of the relations dimG=edimG, dimG<edimG, or dimG>edimG.We consider Jahangir graphJ2n, helm graph Hn, sunflower graph Sfn, and friendship graph Fn for edge metric dimension (NP-hard problem). Our aim is to characterize these families with respect to the nature of edge metric dimension. Moreover, we present closed formulas for edge metric dimension of these graphs. For further reading on metric dimension and edge metric dimension, we refer [19, 24, 25, 26, 27].


## 2. Main Results

### 2.1. Jahangir Graph (J2n)

TheJahangir graph J2n obtained from wheel graph W2n by alternately deleting n spokes. The order of J2n is 2n+1, and the size is 3n. The Jahangir graph is also referred to as gear graph Gn [28]. The metric dimension of Jahangir graph dimJ2n2n/3 is given in [29]. Now, we present some observations for J2n in the form of lemmas which help us to compute its edge metric dimension.Lemma 1.
The central vertexv does not belong to any edge metric basis S of J2n, for n≥6.Proof.
LetJ2n=C2n+K1 be a gear graph of order 2n+1. The vertices of C2n are labeled as v1,v2,v3,…,v2n, and edges of J2n are labeled as ej=vv2j−1 and ei′=vivi+1 for all j∈1,2,…,n and i∈1,2,…,2n−1 as shown in Figure 1. The vertices v2j−1 and v2j are named as major and minor vertices, respectively. Since dej,v=0 and dei′,v=1, v does not belong to any basis of J2n.
LetS=vi1,vi2,…,vir be a basis of J2n and r=S≥2 number of vertices on C2n for n≥6. We say that the pairs of vertices via,via+1 for 1≤i≤r−1 and vir,vi1 are pair of neighboring vertices. We define the gap ga for 1≤a≤r−1 as the set of vertices vjia<j<ia+1 and gr=vj1≤j<iorir<j≤2n. The number of gaps is r and some of which may be empty. If a−b=1 or r−1, then the gaps ga and gb are known as the neighboring gaps. Let du=α and dv=β or du=β and dv=α with α≤β. Then, the gap between u and v is denoted by α−β. The number of vertices between u and v is known as the size of gap. There are three types of gaps observed on C2n of J2n, which are 2−2, 2−3, and 3−3. We represent the major vertices by x∗ in the following proofs.Figure 1
Jahangir graph (J2n). (a) J8. (b). J10.
(a)
(b)Lemma 2.
If S is a basis ofJ2n n≥6, then every 2−2, 2−3, and 3−3 gap of S contains at most 5, 4, and 3 vertices, respectively.Proof.
Letei′=vivi+1 be edges on C2n where i∈1,2,…,2n−1 and ej=vv2j−1 be spokes edges of J2n where j∈1,2,…,n. Suppose that there is a 2−2 gap of S containing seven consecutive vertices x∗i+1,xi+2,…,x∗i+7 of C2n, determined by xi and xi+8 with dx∗i+1=dx∗i+7=3. Then, we have rei+2∣S=rei+3∣S, a contradiction. The existence of a 2−3 gap containing six consecutive vertices of C2n: x∗i+1,xi+2,…,xi+6, determined by xi and x∗i+7 with dx∗i+1=3 and dxi+6=2, it follows that re′i+4S=re′i+5S and reiS=rei+1S.
If there is a3−3 gap of S containing five consecutive vertices xi+1,x∗i+2,…,xi+5 of C2n and determined by x∗i and x∗i+6 with dxi+1=dxi+5=2 would imply rei+1∣S=rei+2∣S and re′i+2∣S=re′i+3∣S, a contradiction.
Hence, it is proved that every2−2, 2−3, and 3−3 gap of S contains at most 5, 4, and 3 vertices, respectively.
Note that these2−2, 2−3, and 3−3 gaps are the known major gaps.Lemma 3.
If S is a basis ofJ2n (n≥6), then it contains at most one major gap.Proof.
Suppose that S contains two distinct major gapsga and gb.(i)
3−3 and 3−3: xi+1,x∗i+2,xi+3 and yj+1,y∗j+2,yj+3, it follows rei+1∣S=rei+3∣S and re′i+3∣S=re′i+4∣S(ii)
3−3 and 2−2: xi+1,x∗i+2,xi+3 and y∗j+1,yj+2,y∗j+3,yj+4,y∗j+5; in this case rei+1∣S=rei+4∣S(iii)
3−3 and 2−3: xi+1,x∗i+2,xi+3 and y∗j+1,yj+2,y∗j+3,yj+5; we have rei+1∣S=rei+3∣S and re′i+3∣S=re′i+4∣S(iv)
2−2 and 2−2: x∗i+1,xi+2,x∗i+3,xi+4,x∗i+5 and y∗j+1,yj+2,y∗j+3,yj+4,y∗j+5; in this case, rei+2∣S=rei+5∣S, rei+3∣S=rei+4∣S, and re′i+4∣S=re′i+9∣S(v)
2−2 and 2−3: x∗i+1,xi+2,x∗i+3,xi+4,x∗i+5 and y∗j+1,yj+2,y∗j+3,yj+4; in this case, rei+2∣S=rei+5∣S, rei+3∣S=rei+4∣S, and re′i+4∣S=re′i+9∣S(vi)
2−3 and 2−3: x∗i+1,xi+2,x∗i+3,xi+4 and y∗j+1,yj+2,y∗j+3,yj+4; in this case, rei∣S=rei+1∣S, rei+2∣S=rei+5∣S, and rei′∣S=re′i+1∣S, which contradicts the hypothesis.Lemma 4.
Ifn≥6 and S be a basis of J2n. Then, any two neighboring gaps, one of which being a major gap, contain together at most six vertices.Proof.
If we take a3−3 gap which contains three vertices, then its neighboring gap should contain three vertices that is only possible when we take 3−3 as a neighboring gap, which is not possible because Lemma 2 says that the basis only contains one major gap.
If we take major2−2 gap with five vertices, then the neighboring cannot be a minor 2−2 gap with three vertices or minor 2−3 gap with two vertices, we show them below case wise:Case 1. The vertices of gaps ga and gb are x∗i+1,xi+2,x∗i+3,xi+4,x∗i+5 and x∗i+7,xi+8,x∗i+9, respectively, and determined by xi, xi+6, and xi+10, then we have rei+3∣S=rei+4∣S and re′i+6∣S=re′i+8∣S, a contradiction.Case 2. The vertices of gaps ga and gb are x∗i+1,xi+2,x∗i+3,xi+4,x∗i+5 and x∗i+7,xi+8, respectively, determined by xi, xi+6, and x∗i+9, then we have rei∣S=rei+1∣S and rei′∣S=re′i+1∣S.
If the gap is2−3 gap with four vertices, then Lemma 2 is sufficient to show the neighboring gap cannot be minor 2−2 gap with three vertices. In this case, the gaps ga and gb vertices are x∗i+1,xi+2,x∗i+3,xi+4 and x∗i−1,xi−2,x∗i−3, respectively, so rei∣S=rei+1∣S and re′i+2∣S=re′i+3∣S.Lemma 5.
If S is a basis ofJ2n (n≥6), then any two minor neighboring gaps contain together at most four vertices.Proof.
Since by Lemma 2 any minor2−2, 2−3, and 3−3 gap contains 3, 2, and 1 vertexes, respectively, it is sufficient to consider the following cases:Case 1. A 2−2 gap with 3 vertices has a neighboring 2−2 gap with 3 vertices.Case 2. A 2−2 gap with 3 vertices having a neighboring 2−3 gap with 2 vertices cannot occur.
If Case 1 holds, thenrei∣S=rei+1∣S and rei′∣S=re′i+1∣S, and if Case 2 holds, then rei∣S=rei+1∣S and rei′∣S=re′i+1∣S, so there are contradictions.Theorem 1.
Ifn≥6, then edimJ2n=2n/3.Proof.
We can easily see thatedimJ8=2, in this case, the possible resolving sets are v2,v4, v4,v6, and v6,v8. Similarly, we can also see that edimJ10=3. First, we show that edimJ2n≤2n/3 by constructing a resolving set in J2n with 2n/3 vertices. We consider three cases according to the residue classes of modulo 3, where n belongs to the following cases.Case 1. n≡0mod3. Let 2n=3k, where k is even, k≥4, and 2n/3=k. In this case, S=v6i−4,v6i:1≤i≤k/2−1∪v1,v2n−4.Case 2. n≡1mod3. Let 2n=3k+2, where k is even, k≥4, and 2n/3=k. We define S=v6i−2,v6i+2:1≤i≤k/2−1∪v2,v2n−4.Case 3. n≡2mod3. Let 2n=3k+1, where k is odd, k≥5, and 2n/3=k and S=v6i−2,v6i:1≤i≤k−1/2∪v1.
The setS contains only one major gap, and remaining gaps are minor gaps which are 2−2, 2−3, and 3−3 gaps containing 3, 2, and 1 number of vertices, respectively. The total number of vertices in any two neighboring gaps, one of which is major, are at most 6 (Lemma 4). Any two neighboring gaps contain at most 4 vertices (Lemma 5). Now, we show that edimJ2n≥2n/3. Let S be a basis of J2n and S=r. Then, S induces r gaps on C2n, denoted as g1,…,gr such that gi and gi+1 for every 1≤i≤r−1 and also g1 and gr are neighboring gaps. By Lemma 3, at most one of them, say g1 is a major gap. By Lemma 4, we can write g1+g2≤6, gr+g1≤6, and by Lemma 5, the relation for the remaining neighboring gaps is gi+gi+1≤4 for every i=2,…,r−1.
So, we have(1)22n−r=2∑i=1rgi≤4r=2+12,22n−r≤4r+4,r≥2n−23≥2n3.
Sincer∈ℕ, for each n≡0,1or2mod3, we obtain r≥2n/3.


### 2.2. Helm Graph (Hn)

Thehelm graph Hn is obtained from wheel graph Wn by adding a single pendant edge at each vertex of cycle Cn. The number of vertices in the helm graph are V=2n+1, and the number of edges are E=3n. We labeled the central vertex, cycle vertices, and pendant vertices as v, vi, and vi′, respectively, where 1≤i≤n. There are three types of edges, and we labeled them in such a way ei=vvi, ei′=vivi+1, and ei″=vivi′, see Figure 2.Figure 2
Helm graph (Hn). (a) H5. (b). Hn.
(a)
(b)In [30], it was proved that the metric dimension of the helm graph is unbounded, i.e., dimHn=2n+2/5.Theorem 2.
LetHn be a helm graph. Then,(2)edimHn=n,n=3,4,n−1,n≥5.Proof.
Ifn=3 or 4, then the proof is simple. Let n≥5 and VHn=v,v1,v2,…,vn,v1′,v2′,…,vn′, where dv=n, vertices vi are on Cn and they have degree 4, i.e., dvi=4, and the vi′ are the pendant vertices having dvi=1. To prove that S is a minimum edge resolving set, we consider the following three cases:(1)
Ifei=vvi, then ei has distance 0 to vi and distance 1 to vj, where j∈1,2,…,n and j≠i, distance 1 to vi′ and distance 2 to vj′, where j∈1,2,…,n and j≠i.(2)
Ifei′=vivi+1, then ei′ has distance 0 to vi and vi+1, distance 1 to v,vi−1,vi+2, distance 2 to all other vertices on Cn, distance 1 to vi′,vi+1′, distance 2 to vi−1′,vi+2′, and distance 3 to all other pendant vertices.(3)
Ifei″=vivi′, then ei″ has distance 0 to vi and vi′, distance 1 to v,vi−1,vi+1, distance 2 to vi−1′,vi+1′, and distance 3 to all other pendant vertices.
The above cases show that the edge metric representation with anyn−2 vertices or less number of vertices of Hn is same for some edges. So, S is the edge metric generator with n−1 vertices, and therefore,(3)edimHn≤n−1.
We can also show that theedimHn≰n−2 by considering S as a basis of Hn with S=n−2. For this we have the following cases:(i)
If we takeS=vi,vi+1,…,vn−2, then rei−1∣S=ren−1∣S.(ii)
If we supposeS=vi′,vi+1′,…,vn−2′, then rei−1∣S=ren−1∣S.(iii)
If we considerS=vi′,…,vi+n−4′,vi+n−3′ and S=vi′,vi+1′,…,vi+n−3′, then rei∣S=rei′∣S and rei+1S=rei+2∣S, respectively.
So, setS is not the basis of Hn. This implies that(4)edimHn≥n−1.
Hence, from inequalities (3) and (4), we have edimHn=n−1.
Note. The total number of edge resolving sets for the helm graph (Hn) is n+1.


### 2.3. Sunflower Graph (Sfn)

Thesunflower graph Sfn obtained from wheel graph (Wn) having a cycle Cn (v1,v2,…,vn) and by adding n new vertices v1′,v2′,…,vn′ with new edges (vi′,vi) and (vi′,vi+1) where 1≤i≤n are shown in Figure 3. The number of vertices in the sunflower graph are V=2n+1, and the number of edges are E=4n. We labeled the central vertex, cycle vertices, and the newly added vertices by v, vi, and vi′, respectively, where 1≤i≤n. We denote the cycle v1,v1′,v2,v2′,…,vn′,v1 by C2n′. There are three types of edges and we label them in the following manner, ei=vvi, ei′=vivi+1, and ei″=vivi′ or ei″=vi+1vi′, consider Figure 3 for reference.The metric dimension of the sunflower graph forn≥6,(5)dimSfn=n3,n≡0mod3,n−13,ifnis odd,n+13,ifnis even,,n≡1mod3,n+13,n≡2mod3.Figure 3
Sunflower graph (Sf6).Now, we present some observations forSfn to prove its edge metric dimension.(i)
There are two edge disjoint cycles:Cn:v1e1′v2e2′v3⋯en−1′vnen′v1 and C2n′:v1e1″v1′e2″v2⋯vne2n−1″vn′e2n″v1.(ii)
Every2−2 gap of S contains one vertex vi or three vertices vi,vi′,vi+1 of Cn and C2n′, respectively.(iii)
There are three types of gaps, namely,2−2, 2−5, and 5−5 with the maximum gap of sizes 3, 2, and 0, respectively.(iv)
The resolving setS contains two 2−5 gaps of sizes 2 and 0, when n≡2mod3.(v)
The resolving setS mostly contains 2−2 gaps.(vi)
Any two2−2 neighboring gaps contain together at most 4 number of vertices.(vii)
The neighboring2−2 and 2−5 gaps contain together at most 3 number of vertices.(viii)
Only one vertex of degree 5 fromCn belongs to edge resolving set S of Sfn, when n≡2mod3 and all remaining vertices belong to C2n′. If we consider any two consecutive vertices of the degree 5 in basis set S such as vi and vi+1, then re′i+1∣S=re′i+2∣S=1,0,2,3,…,3 and rei′∣S=rei−1S=0,1,3,…,3,2. So, the 5−5 gap is not possible in the sunflower graph for edge metric dimension.(ix)
Any two2−5 neighboring gaps contain together at most 2 vertices. If there are 4 vertices in 2−5 neighboring gaps for vi∈S where 1≤i≤2n, then re′i+1∣S=re′i+3∣S=1,1,2,…,2, rei−1′∣S=rei′∣S=1,2,…,1,2, and re2n″∣S=ren′∣S=0,2,3,…,3.(x)
The central vertexv does not belong to any edge metric basis S of Sfn because dei,v=0, dei′,v=1, and dej″,v=1 where 1≤i≤n and 1≤j≤2n.We can also define the selection of basisS of Sfn by the following Claims.Claim 1.
The resolving set S mostly contains2−2 gaps having one vertex.
If a gapg of the size 1 with vertex vi+1 on Cn and vi′,vi+1′,vi+3′,vi+4′∈S, then g contains two edges ei+1″=vi′vi+1 and ei+2″=vi+1vi+1′ on C2n′. If z∈ei+1″,ei+2″ then(6)rzS=1,0,1,2,…,2,0,1,2,3,…,3,2¯,rzS=1,0,1,2,…,2,1,0,2,3,…,3,2¯,where the normal part of the code and overlined part of the code represent the distance of z from vi and vi′ types of vertices, respectively.
By observationv and Claim 1, there is no other edge in Sfn having these types of codes.Claim 2.
At most one2−2 gap of S has at most 3 number of vertices.
If a gapg of the size 3 with vertices vi+3,vi+3′,vi+4, on C2n′ and vi′, vi+1′, vi+2′, vi+4′, vi+5′∈S, then the g contains 5 number of edges, one of them e′i+3=vi+3vi+4 on Cn and 4 of them ei+5″=vi+2′vi+3, ei+6″=vi+3vi+3′, ei+7″=vi+3′vi+4, ei+8″=vi+4vi+4′ on C2n′. If z∈e′i+3,ei+5″,ei+6″,ei+7″,ei+8″, then(7)rzS=2,2,1,0,0,1,2,…,2,3,2,1,1,1,2,3,…,3¯,rzS=2,2,1,0,1,2,…,2,3,2,0,1,2,3,…,3¯,rzS=2,2,1,0,1,2,…,2,3,2,1,0,2,3,…,3¯,rzS=2,2,2,1,0,1,2,…,2,3,3,2,0,1,3,…,3¯,rzS=2,2,2,1,0,1,2,…,2,3,3,2,1,0,2,3,…,3¯,where the normal part of the code and overlined part of the code represent the distance of z from vi and vi′ types of vertices, respectively.
By observation iii and Claim 2, there is no other edge inSfn with these types of codes.Claim 3.
At most one2−5 gap of S has 2 vertices.
If a gapg of the size 2 with vertices vn,vn′, and vn−7′,vn−6′,vn−4′,vn−2′,vn−1′,vn+1=vi∈S, then the g contains 4 number of edges, one of them en′=vnvn+1 on Cn and 3 of them e2n−2″=vn−1′vn, e2n−1″=vnvn′, e2n−1″=vn′vn+1 on C2n′. If z z∈en′,e2n−2″,e2n−1″,e2n″, then(8)rzS=0,1,2,…,2,1,0,1,2,3,…,3,2,1,1¯,rzS=1,2,…,2,1,0,2,3,…,3,2,0,1¯,rzS=1,2,…,2,1,0,2,3,…,3,2,1,0¯,rzS=0,1,2,…,2,0,1,1,2,3,…,3,2,1¯,where the normal part of the code and overlined part of the code represent the distance of z from vi and vi′ types of vertices, respectively.
By observations iii and iv and Claim 3, there is no other edge inSfn with these type of codes.Claim 4.
Any two,2−2 neighboring gaps contain together at most 4 number of vertices.
Let two2−2 neighboring gaps ga and gb have 1 and 3 number of vertices, respectively. The gaps ga and gb are determined by vi′, vi+2′, and vi+3′. The gap ga has one vertex vi+2 and two edges ei+3″=vi+1′vi+2, ei+4″=vi+2vi+2′ on C2n′. The gb has 3 vertices vi+3, vi+3′, and vi+4 and 5 number of edges, one of them e′i+3=vi+3vi+4 on Cn and 4 of them ei+5″=vi+2′vi+3, ei+6″=vi+3vi+3′, ei+7″=vi+3′vi+4, ei+8″=vi+4vi+4′ on C2n′. If vi′,vi+1′,vi+2′,vi+4′,vi+5′∈S and z z∈ei+3″,e′i+3,ei+4″,e′i+5,e′i+6,e′i+7,e′i+8, then(9)rzS=2,1,0,1,2,…,2,2,0,1,2,3,…,3¯,rzS=2,2,1,0,0,1,2,…,2,3,2,1,1,1,2,3,…,3¯,rzS=2,1,0,1,2,….,2,2,1,0,2,3,…,3¯,rzS=2,2,1,0,1,2,…,2,3,3,2,0,1,3,…,3¯,rzS=2,2,1,0,1,2,…,2,3,2,1,0,2,3,…,3¯,rzS=2,2,2,1,0,1,2,…,2,3,3,2,0,1,3,…,3¯,rzS=2,2,2,1,0,1,2,…,2,3,3,2,1,0,2,3,…,3¯,where the normal part of the code and overlined part of the code represent the distance of z from vi and vi′ types of vertices, respectively.
By observations iii, v, and vi and Claim 4, there is no other edge inSfn having these types of codes.Claim 5.
The neighboring2−2 and 2−5 gaps contain together at most 3 number of vertices.
Letga and gb be 2−2 and 2−5 neighboring gaps having 1 and 2 vertices, respectively. These gaps can be determined by vi−7′, vn−1′, and vn+1. The gap ga has one vertex vn−1 on Cn or two edges e2n−3″=vn−1′vn−1, e2n−4″=vn−1vn′ on C2n′. The gb has 2 vertices vn, vn′ and 4 number of edges, one of them en′=vnvn+1 on Cn and 3 of them e2n−2″=vn−1′vn, e2n−1″=vnvn′, and e2n″=vn′vn+1 on C2n′. If vn−7′,vn−6′,vn−4′,vn−2′,vn−1′,vn+1′=vi∈S and z∈en′,e2n−4″,e2n−3″,e2n−2″,e2n−1″,e2n″, then(10)rzS=0,1,2,…,2,1,0,1,2,3,…,3,2,1,1¯,rzS=2,…,2,1,0,1,3,…,3,2,0,1,2¯,rzS=2,…,2,1,0,1,1,0,3,…,3,2,1,0,2¯,rzS=1,2,…,2,1,0,2,3,…,3,2,0,1¯,rzS=1,2,…,2,1,0,2,3,…,3,2,1,0¯,rzS=0,1,2,…,2,0,1,1,2,3,…,3,2,1¯,where the normal part of the code and overlined part of the code represent distance of z from vi and vi′ types of vertices, respectively.
By observations iii, v, and vii and Claim 5, there is no other edge inSfn with these types of codes.Theorem 3.
Ifn≥6, then edimSfn=2n/3.Proof.
The resolving set forSf5 is S=v2,v3,v7,v9,v10.
First, we show thatedimSfn≤2n/3 for n≥6 by constructing a resolving set for Sfn with 2n/3 vertices. We consider three cases according to the residue class modulo 3 to which n belongs.Case 1. n≡0mod3. Let 2n=3k, where k is even, k≥4, and 2n/3=k. In this case, S=v3i−1′,v3i′:1≤i≤k/2−1∪vn−1′,vn′.Case 2. n≡1mod3. Let 2n=3k+2, where k is even, k≥4, and 2n/3=k. We define S=v3i′,v3i+1′:1≤i≤k/2−1∪vn+2′.Case 3. n≡2mod3. Let 2n=3k+1, where k is odd, k≥5, and 2n/3=k and S=v3i+2′,v3i+2′:1≤i≤k/2−1∪vn+2′.
To show thatedimSfn≥2n/3, we consider the aforementioned observations.
LetS be a basis of Sfn and S=r. Then, S induces r gaps which are denoted as g1,…,gr such that gi and gi+1 for every 1≤i≤r−1 and also g1 and gr are neighboring gaps. We can write g1+g2≤3, gr+g1≤3 and the relation for the remaining neighboring gaps is gi+gi+1≤3 for every i=2,…,r−1.
So, we have(11)22n−r=2∑i=1rgi≤4r−2+6,22n−r≤4r−2,r≥4n+26=2n3+13≥2n3.
Sincer∈ℕ, for each n≡0,1or2mod3, we obtain r≥2n/3 Hence, the theorem is proved.


### 2.4. Friendship Graph (Fn)

Thefriendship graph Fn can be obtained from the wheel graph by removing the alternative edges of the Cn cycle of Wn. The number of vertices in the friendship graph are V=2n+1, and the number of edges are E=3n. We label the central vertex and remaining vertices as v and vi, respectively, where 1≤i≤2n. There are two types of edges, and we label them in such a way ei=vvi and ej′=v2j−1v2j where j∈1,2,…,n, for reference, see Figure 4Figure 4
Friendship graph (F4).The metric dimension of friendship graphdimFn=n for n≥2, computed by Mulyono and Wulandari in [31].Theorem 4.
LetFn be a friendship graph, then edimFn=2n−1 for n≥3.Proof.
Letn≥3 and VFn=v,v1,v2,…,v2n, where dv=2n and dvi=2, where i∈1,2,…,2n. To prove that S is a minimum edge resolving set, we consider the following three cases:Case 1. If ei=vvi, then ei has distance 0 to v,vi and distance 1 to all other vertices, where i∈1,2,…,2n.Case 2. If ei′=vivi+1, then ei′ has distance 0 to vi and vi+1 distance 1 to v, distance 2 to all other vertices.
The above cases show that the edge metric representation of edges ofG≅Fn with respect to a set with 2n−2 vertices is not distinct. So S can be edge metric generator if we take 2n−1 number of vertices. Therefore, the edge metric dimension of the friendship graph is 2n−1.
We also show that the by considering the resolving set,S of the size 2n−2. Let S=vi,vi+1,…,v2n−2, then ren−1∣S=ren∣S or rei∣S=ren∣S. So set S is not the basis of Fn. Hence, it is proved that edimFn=2n−1.
Note. The total number of edge resolving sets for a fan graph (Fn) is 2n.


## 2.1. Jahangir Graph (J2n)

TheJahangir graph J2n obtained from wheel graph W2n by alternately deleting n spokes. The order of J2n is 2n+1, and the size is 3n. The Jahangir graph is also referred to as gear graph Gn [28]. The metric dimension of Jahangir graph dimJ2n2n/3 is given in [29]. Now, we present some observations for J2n in the form of lemmas which help us to compute its edge metric dimension.Lemma 1.
The central vertexv does not belong to any edge metric basis S of J2n, for n≥6.Proof.
LetJ2n=C2n+K1 be a gear graph of order 2n+1. The vertices of C2n are labeled as v1,v2,v3,…,v2n, and edges of J2n are labeled as ej=vv2j−1 and ei′=vivi+1 for all j∈1,2,…,n and i∈1,2,…,2n−1 as shown in Figure 1. The vertices v2j−1 and v2j are named as major and minor vertices, respectively. Since dej,v=0 and dei′,v=1, v does not belong to any basis of J2n.
LetS=vi1,vi2,…,vir be a basis of J2n and r=S≥2 number of vertices on C2n for n≥6. We say that the pairs of vertices via,via+1 for 1≤i≤r−1 and vir,vi1 are pair of neighboring vertices. We define the gap ga for 1≤a≤r−1 as the set of vertices vjia<j<ia+1 and gr=vj1≤j<iorir<j≤2n. The number of gaps is r and some of which may be empty. If a−b=1 or r−1, then the gaps ga and gb are known as the neighboring gaps. Let du=α and dv=β or du=β and dv=α with α≤β. Then, the gap between u and v is denoted by α−β. The number of vertices between u and v is known as the size of gap. There are three types of gaps observed on C2n of J2n, which are 2−2, 2−3, and 3−3. We represent the major vertices by x∗ in the following proofs.Figure 1
Jahangir graph (J2n). (a) J8. (b). J10.
(a)
(b)Lemma 2.
If S is a basis ofJ2n n≥6, then every 2−2, 2−3, and 3−3 gap of S contains at most 5, 4, and 3 vertices, respectively.Proof.
Letei′=vivi+1 be edges on C2n where i∈1,2,…,2n−1 and ej=vv2j−1 be spokes edges of J2n where j∈1,2,…,n. Suppose that there is a 2−2 gap of S containing seven consecutive vertices x∗i+1,xi+2,…,x∗i+7 of C2n, determined by xi and xi+8 with dx∗i+1=dx∗i+7=3. Then, we have rei+2∣S=rei+3∣S, a contradiction. The existence of a 2−3 gap containing six consecutive vertices of C2n: x∗i+1,xi+2,…,xi+6, determined by xi and x∗i+7 with dx∗i+1=3 and dxi+6=2, it follows that re′i+4S=re′i+5S and reiS=rei+1S.
If there is a3−3 gap of S containing five consecutive vertices xi+1,x∗i+2,…,xi+5 of C2n and determined by x∗i and x∗i+6 with dxi+1=dxi+5=2 would imply rei+1∣S=rei+2∣S and re′i+2∣S=re′i+3∣S, a contradiction.
Hence, it is proved that every2−2, 2−3, and 3−3 gap of S contains at most 5, 4, and 3 vertices, respectively.
Note that these2−2, 2−3, and 3−3 gaps are the known major gaps.Lemma 3.
If S is a basis ofJ2n (n≥6), then it contains at most one major gap.Proof.
Suppose that S contains two distinct major gapsga and gb.(i)
3−3 and 3−3: xi+1,x∗i+2,xi+3 and yj+1,y∗j+2,yj+3, it follows rei+1∣S=rei+3∣S and re′i+3∣S=re′i+4∣S(ii)
3−3 and 2−2: xi+1,x∗i+2,xi+3 and y∗j+1,yj+2,y∗j+3,yj+4,y∗j+5; in this case rei+1∣S=rei+4∣S(iii)
3−3 and 2−3: xi+1,x∗i+2,xi+3 and y∗j+1,yj+2,y∗j+3,yj+5; we have rei+1∣S=rei+3∣S and re′i+3∣S=re′i+4∣S(iv)
2−2 and 2−2: x∗i+1,xi+2,x∗i+3,xi+4,x∗i+5 and y∗j+1,yj+2,y∗j+3,yj+4,y∗j+5; in this case, rei+2∣S=rei+5∣S, rei+3∣S=rei+4∣S, and re′i+4∣S=re′i+9∣S(v)
2−2 and 2−3: x∗i+1,xi+2,x∗i+3,xi+4,x∗i+5 and y∗j+1,yj+2,y∗j+3,yj+4; in this case, rei+2∣S=rei+5∣S, rei+3∣S=rei+4∣S, and re′i+4∣S=re′i+9∣S(vi)
2−3 and 2−3: x∗i+1,xi+2,x∗i+3,xi+4 and y∗j+1,yj+2,y∗j+3,yj+4; in this case, rei∣S=rei+1∣S, rei+2∣S=rei+5∣S, and rei′∣S=re′i+1∣S, which contradicts the hypothesis.Lemma 4.
Ifn≥6 and S be a basis of J2n. Then, any two neighboring gaps, one of which being a major gap, contain together at most six vertices.Proof.
If we take a3−3 gap which contains three vertices, then its neighboring gap should contain three vertices that is only possible when we take 3−3 as a neighboring gap, which is not possible because Lemma 2 says that the basis only contains one major gap.
If we take major2−2 gap with five vertices, then the neighboring cannot be a minor 2−2 gap with three vertices or minor 2−3 gap with two vertices, we show them below case wise:Case 1. The vertices of gaps ga and gb are x∗i+1,xi+2,x∗i+3,xi+4,x∗i+5 and x∗i+7,xi+8,x∗i+9, respectively, and determined by xi, xi+6, and xi+10, then we have rei+3∣S=rei+4∣S and re′i+6∣S=re′i+8∣S, a contradiction.Case 2. The vertices of gaps ga and gb are x∗i+1,xi+2,x∗i+3,xi+4,x∗i+5 and x∗i+7,xi+8, respectively, determined by xi, xi+6, and x∗i+9, then we have rei∣S=rei+1∣S and rei′∣S=re′i+1∣S.
If the gap is2−3 gap with four vertices, then Lemma 2 is sufficient to show the neighboring gap cannot be minor 2−2 gap with three vertices. In this case, the gaps ga and gb vertices are x∗i+1,xi+2,x∗i+3,xi+4 and x∗i−1,xi−2,x∗i−3, respectively, so rei∣S=rei+1∣S and re′i+2∣S=re′i+3∣S.Lemma 5.
If S is a basis ofJ2n (n≥6), then any two minor neighboring gaps contain together at most four vertices.Proof.
Since by Lemma 2 any minor2−2, 2−3, and 3−3 gap contains 3, 2, and 1 vertexes, respectively, it is sufficient to consider the following cases:Case 1. A 2−2 gap with 3 vertices has a neighboring 2−2 gap with 3 vertices.Case 2. A 2−2 gap with 3 vertices having a neighboring 2−3 gap with 2 vertices cannot occur.
If Case 1 holds, thenrei∣S=rei+1∣S and rei′∣S=re′i+1∣S, and if Case 2 holds, then rei∣S=rei+1∣S and rei′∣S=re′i+1∣S, so there are contradictions.Theorem 1.
Ifn≥6, then edimJ2n=2n/3.Proof.
We can easily see thatedimJ8=2, in this case, the possible resolving sets are v2,v4, v4,v6, and v6,v8. Similarly, we can also see that edimJ10=3. First, we show that edimJ2n≤2n/3 by constructing a resolving set in J2n with 2n/3 vertices. We consider three cases according to the residue classes of modulo 3, where n belongs to the following cases.Case 1. n≡0mod3. Let 2n=3k, where k is even, k≥4, and 2n/3=k. In this case, S=v6i−4,v6i:1≤i≤k/2−1∪v1,v2n−4.Case 2. n≡1mod3. Let 2n=3k+2, where k is even, k≥4, and 2n/3=k. We define S=v6i−2,v6i+2:1≤i≤k/2−1∪v2,v2n−4.Case 3. n≡2mod3. Let 2n=3k+1, where k is odd, k≥5, and 2n/3=k and S=v6i−2,v6i:1≤i≤k−1/2∪v1.
The setS contains only one major gap, and remaining gaps are minor gaps which are 2−2, 2−3, and 3−3 gaps containing 3, 2, and 1 number of vertices, respectively. The total number of vertices in any two neighboring gaps, one of which is major, are at most 6 (Lemma 4). Any two neighboring gaps contain at most 4 vertices (Lemma 5). Now, we show that edimJ2n≥2n/3. Let S be a basis of J2n and S=r. Then, S induces r gaps on C2n, denoted as g1,…,gr such that gi and gi+1 for every 1≤i≤r−1 and also g1 and gr are neighboring gaps. By Lemma 3, at most one of them, say g1 is a major gap. By Lemma 4, we can write g1+g2≤6, gr+g1≤6, and by Lemma 5, the relation for the remaining neighboring gaps is gi+gi+1≤4 for every i=2,…,r−1.
So, we have(1)22n−r=2∑i=1rgi≤4r=2+12,22n−r≤4r+4,r≥2n−23≥2n3.
Sincer∈ℕ, for each n≡0,1or2mod3, we obtain r≥2n/3.


## 2.2. Helm Graph (Hn)

Thehelm graph Hn is obtained from wheel graph Wn by adding a single pendant edge at each vertex of cycle Cn. The number of vertices in the helm graph are V=2n+1, and the number of edges are E=3n. We labeled the central vertex, cycle vertices, and pendant vertices as v, vi, and vi′, respectively, where 1≤i≤n. There are three types of edges, and we labeled them in such a way ei=vvi, ei′=vivi+1, and ei″=vivi′, see Figure 2.Figure 2
Helm graph (Hn). (a) H5. (b). Hn.
(a)
(b)In [30], it was proved that the metric dimension of the helm graph is unbounded, i.e., dimHn=2n+2/5.Theorem 2.
LetHn be a helm graph. Then,(2)edimHn=n,n=3,4,n−1,n≥5.Proof.
Ifn=3 or 4, then the proof is simple. Let n≥5 and VHn=v,v1,v2,…,vn,v1′,v2′,…,vn′, where dv=n, vertices vi are on Cn and they have degree 4, i.e., dvi=4, and the vi′ are the pendant vertices having dvi=1. To prove that S is a minimum edge resolving set, we consider the following three cases:(1)
Ifei=vvi, then ei has distance 0 to vi and distance 1 to vj, where j∈1,2,…,n and j≠i, distance 1 to vi′ and distance 2 to vj′, where j∈1,2,…,n and j≠i.(2)
Ifei′=vivi+1, then ei′ has distance 0 to vi and vi+1, distance 1 to v,vi−1,vi+2, distance 2 to all other vertices on Cn, distance 1 to vi′,vi+1′, distance 2 to vi−1′,vi+2′, and distance 3 to all other pendant vertices.(3)
Ifei″=vivi′, then ei″ has distance 0 to vi and vi′, distance 1 to v,vi−1,vi+1, distance 2 to vi−1′,vi+1′, and distance 3 to all other pendant vertices.
The above cases show that the edge metric representation with anyn−2 vertices or less number of vertices of Hn is same for some edges. So, S is the edge metric generator with n−1 vertices, and therefore,(3)edimHn≤n−1.
We can also show that theedimHn≰n−2 by considering S as a basis of Hn with S=n−2. For this we have the following cases:(i)
If we takeS=vi,vi+1,…,vn−2, then rei−1∣S=ren−1∣S.(ii)
If we supposeS=vi′,vi+1′,…,vn−2′, then rei−1∣S=ren−1∣S.(iii)
If we considerS=vi′,…,vi+n−4′,vi+n−3′ and S=vi′,vi+1′,…,vi+n−3′, then rei∣S=rei′∣S and rei+1S=rei+2∣S, respectively.
So, setS is not the basis of Hn. This implies that(4)edimHn≥n−1.
Hence, from inequalities (3) and (4), we have edimHn=n−1.
Note. The total number of edge resolving sets for the helm graph (Hn) is n+1.


## 2.3. Sunflower Graph (Sfn)

Thesunflower graph Sfn obtained from wheel graph (Wn) having a cycle Cn (v1,v2,…,vn) and by adding n new vertices v1′,v2′,…,vn′ with new edges (vi′,vi) and (vi′,vi+1) where 1≤i≤n are shown in Figure 3. The number of vertices in the sunflower graph are V=2n+1, and the number of edges are E=4n. We labeled the central vertex, cycle vertices, and the newly added vertices by v, vi, and vi′, respectively, where 1≤i≤n. We denote the cycle v1,v1′,v2,v2′,…,vn′,v1 by C2n′. There are three types of edges and we label them in the following manner, ei=vvi, ei′=vivi+1, and ei″=vivi′ or ei″=vi+1vi′, consider Figure 3 for reference.The metric dimension of the sunflower graph forn≥6,(5)dimSfn=n3,n≡0mod3,n−13,ifnis odd,n+13,ifnis even,,n≡1mod3,n+13,n≡2mod3.Figure 3
Sunflower graph (Sf6).Now, we present some observations forSfn to prove its edge metric dimension.(i)
There are two edge disjoint cycles:Cn:v1e1′v2e2′v3⋯en−1′vnen′v1 and C2n′:v1e1″v1′e2″v2⋯vne2n−1″vn′e2n″v1.(ii)
Every2−2 gap of S contains one vertex vi or three vertices vi,vi′,vi+1 of Cn and C2n′, respectively.(iii)
There are three types of gaps, namely,2−2, 2−5, and 5−5 with the maximum gap of sizes 3, 2, and 0, respectively.(iv)
The resolving setS contains two 2−5 gaps of sizes 2 and 0, when n≡2mod3.(v)
The resolving setS mostly contains 2−2 gaps.(vi)
Any two2−2 neighboring gaps contain together at most 4 number of vertices.(vii)
The neighboring2−2 and 2−5 gaps contain together at most 3 number of vertices.(viii)
Only one vertex of degree 5 fromCn belongs to edge resolving set S of Sfn, when n≡2mod3 and all remaining vertices belong to C2n′. If we consider any two consecutive vertices of the degree 5 in basis set S such as vi and vi+1, then re′i+1∣S=re′i+2∣S=1,0,2,3,…,3 and rei′∣S=rei−1S=0,1,3,…,3,2. So, the 5−5 gap is not possible in the sunflower graph for edge metric dimension.(ix)
Any two2−5 neighboring gaps contain together at most 2 vertices. If there are 4 vertices in 2−5 neighboring gaps for vi∈S where 1≤i≤2n, then re′i+1∣S=re′i+3∣S=1,1,2,…,2, rei−1′∣S=rei′∣S=1,2,…,1,2, and re2n″∣S=ren′∣S=0,2,3,…,3.(x)
The central vertexv does not belong to any edge metric basis S of Sfn because dei,v=0, dei′,v=1, and dej″,v=1 where 1≤i≤n and 1≤j≤2n.We can also define the selection of basisS of Sfn by the following Claims.Claim 1.
The resolving set S mostly contains2−2 gaps having one vertex.
If a gapg of the size 1 with vertex vi+1 on Cn and vi′,vi+1′,vi+3′,vi+4′∈S, then g contains two edges ei+1″=vi′vi+1 and ei+2″=vi+1vi+1′ on C2n′. If z∈ei+1″,ei+2″ then(6)rzS=1,0,1,2,…,2,0,1,2,3,…,3,2¯,rzS=1,0,1,2,…,2,1,0,2,3,…,3,2¯,where the normal part of the code and overlined part of the code represent the distance of z from vi and vi′ types of vertices, respectively.
By observationv and Claim 1, there is no other edge in Sfn having these types of codes.Claim 2.
At most one2−2 gap of S has at most 3 number of vertices.
If a gapg of the size 3 with vertices vi+3,vi+3′,vi+4, on C2n′ and vi′, vi+1′, vi+2′, vi+4′, vi+5′∈S, then the g contains 5 number of edges, one of them e′i+3=vi+3vi+4 on Cn and 4 of them ei+5″=vi+2′vi+3, ei+6″=vi+3vi+3′, ei+7″=vi+3′vi+4, ei+8″=vi+4vi+4′ on C2n′. If z∈e′i+3,ei+5″,ei+6″,ei+7″,ei+8″, then(7)rzS=2,2,1,0,0,1,2,…,2,3,2,1,1,1,2,3,…,3¯,rzS=2,2,1,0,1,2,…,2,3,2,0,1,2,3,…,3¯,rzS=2,2,1,0,1,2,…,2,3,2,1,0,2,3,…,3¯,rzS=2,2,2,1,0,1,2,…,2,3,3,2,0,1,3,…,3¯,rzS=2,2,2,1,0,1,2,…,2,3,3,2,1,0,2,3,…,3¯,where the normal part of the code and overlined part of the code represent the distance of z from vi and vi′ types of vertices, respectively.
By observation iii and Claim 2, there is no other edge inSfn with these types of codes.Claim 3.
At most one2−5 gap of S has 2 vertices.
If a gapg of the size 2 with vertices vn,vn′, and vn−7′,vn−6′,vn−4′,vn−2′,vn−1′,vn+1=vi∈S, then the g contains 4 number of edges, one of them en′=vnvn+1 on Cn and 3 of them e2n−2″=vn−1′vn, e2n−1″=vnvn′, e2n−1″=vn′vn+1 on C2n′. If z z∈en′,e2n−2″,e2n−1″,e2n″, then(8)rzS=0,1,2,…,2,1,0,1,2,3,…,3,2,1,1¯,rzS=1,2,…,2,1,0,2,3,…,3,2,0,1¯,rzS=1,2,…,2,1,0,2,3,…,3,2,1,0¯,rzS=0,1,2,…,2,0,1,1,2,3,…,3,2,1¯,where the normal part of the code and overlined part of the code represent the distance of z from vi and vi′ types of vertices, respectively.
By observations iii and iv and Claim 3, there is no other edge inSfn with these type of codes.Claim 4.
Any two,2−2 neighboring gaps contain together at most 4 number of vertices.
Let two2−2 neighboring gaps ga and gb have 1 and 3 number of vertices, respectively. The gaps ga and gb are determined by vi′, vi+2′, and vi+3′. The gap ga has one vertex vi+2 and two edges ei+3″=vi+1′vi+2, ei+4″=vi+2vi+2′ on C2n′. The gb has 3 vertices vi+3, vi+3′, and vi+4 and 5 number of edges, one of them e′i+3=vi+3vi+4 on Cn and 4 of them ei+5″=vi+2′vi+3, ei+6″=vi+3vi+3′, ei+7″=vi+3′vi+4, ei+8″=vi+4vi+4′ on C2n′. If vi′,vi+1′,vi+2′,vi+4′,vi+5′∈S and z z∈ei+3″,e′i+3,ei+4″,e′i+5,e′i+6,e′i+7,e′i+8, then(9)rzS=2,1,0,1,2,…,2,2,0,1,2,3,…,3¯,rzS=2,2,1,0,0,1,2,…,2,3,2,1,1,1,2,3,…,3¯,rzS=2,1,0,1,2,….,2,2,1,0,2,3,…,3¯,rzS=2,2,1,0,1,2,…,2,3,3,2,0,1,3,…,3¯,rzS=2,2,1,0,1,2,…,2,3,2,1,0,2,3,…,3¯,rzS=2,2,2,1,0,1,2,…,2,3,3,2,0,1,3,…,3¯,rzS=2,2,2,1,0,1,2,…,2,3,3,2,1,0,2,3,…,3¯,where the normal part of the code and overlined part of the code represent the distance of z from vi and vi′ types of vertices, respectively.
By observations iii, v, and vi and Claim 4, there is no other edge inSfn having these types of codes.Claim 5.
The neighboring2−2 and 2−5 gaps contain together at most 3 number of vertices.
Letga and gb be 2−2 and 2−5 neighboring gaps having 1 and 2 vertices, respectively. These gaps can be determined by vi−7′, vn−1′, and vn+1. The gap ga has one vertex vn−1 on Cn or two edges e2n−3″=vn−1′vn−1, e2n−4″=vn−1vn′ on C2n′. The gb has 2 vertices vn, vn′ and 4 number of edges, one of them en′=vnvn+1 on Cn and 3 of them e2n−2″=vn−1′vn, e2n−1″=vnvn′, and e2n″=vn′vn+1 on C2n′. If vn−7′,vn−6′,vn−4′,vn−2′,vn−1′,vn+1′=vi∈S and z∈en′,e2n−4″,e2n−3″,e2n−2″,e2n−1″,e2n″, then(10)rzS=0,1,2,…,2,1,0,1,2,3,…,3,2,1,1¯,rzS=2,…,2,1,0,1,3,…,3,2,0,1,2¯,rzS=2,…,2,1,0,1,1,0,3,…,3,2,1,0,2¯,rzS=1,2,…,2,1,0,2,3,…,3,2,0,1¯,rzS=1,2,…,2,1,0,2,3,…,3,2,1,0¯,rzS=0,1,2,…,2,0,1,1,2,3,…,3,2,1¯,where the normal part of the code and overlined part of the code represent distance of z from vi and vi′ types of vertices, respectively.
By observations iii, v, and vii and Claim 5, there is no other edge inSfn with these types of codes.Theorem 3.
Ifn≥6, then edimSfn=2n/3.Proof.
The resolving set forSf5 is S=v2,v3,v7,v9,v10.
First, we show thatedimSfn≤2n/3 for n≥6 by constructing a resolving set for Sfn with 2n/3 vertices. We consider three cases according to the residue class modulo 3 to which n belongs.Case 1. n≡0mod3. Let 2n=3k, where k is even, k≥4, and 2n/3=k. In this case, S=v3i−1′,v3i′:1≤i≤k/2−1∪vn−1′,vn′.Case 2. n≡1mod3. Let 2n=3k+2, where k is even, k≥4, and 2n/3=k. We define S=v3i′,v3i+1′:1≤i≤k/2−1∪vn+2′.Case 3. n≡2mod3. Let 2n=3k+1, where k is odd, k≥5, and 2n/3=k and S=v3i+2′,v3i+2′:1≤i≤k/2−1∪vn+2′.
To show thatedimSfn≥2n/3, we consider the aforementioned observations.
LetS be a basis of Sfn and S=r. Then, S induces r gaps which are denoted as g1,…,gr such that gi and gi+1 for every 1≤i≤r−1 and also g1 and gr are neighboring gaps. We can write g1+g2≤3, gr+g1≤3 and the relation for the remaining neighboring gaps is gi+gi+1≤3 for every i=2,…,r−1.
So, we have(11)22n−r=2∑i=1rgi≤4r−2+6,22n−r≤4r−2,r≥4n+26=2n3+13≥2n3.
Sincer∈ℕ, for each n≡0,1or2mod3, we obtain r≥2n/3 Hence, the theorem is proved.


## 2.4. Friendship Graph (Fn)

Thefriendship graph Fn can be obtained from the wheel graph by removing the alternative edges of the Cn cycle of Wn. The number of vertices in the friendship graph are V=2n+1, and the number of edges are E=3n. We label the central vertex and remaining vertices as v and vi, respectively, where 1≤i≤2n. There are two types of edges, and we label them in such a way ei=vvi and ej′=v2j−1v2j where j∈1,2,…,n, for reference, see Figure 4Figure 4
Friendship graph (F4).The metric dimension of friendship graphdimFn=n for n≥2, computed by Mulyono and Wulandari in [31].Theorem 4.
LetFn be a friendship graph, then edimFn=2n−1 for n≥3.Proof.
Letn≥3 and VFn=v,v1,v2,…,v2n, where dv=2n and dvi=2, where i∈1,2,…,2n. To prove that S is a minimum edge resolving set, we consider the following three cases:Case 1. If ei=vvi, then ei has distance 0 to v,vi and distance 1 to all other vertices, where i∈1,2,…,2n.Case 2. If ei′=vivi+1, then ei′ has distance 0 to vi and vi+1 distance 1 to v, distance 2 to all other vertices.
The above cases show that the edge metric representation of edges ofG≅Fn with respect to a set with 2n−2 vertices is not distinct. So S can be edge metric generator if we take 2n−1 number of vertices. Therefore, the edge metric dimension of the friendship graph is 2n−1.
We also show that the by considering the resolving set,S of the size 2n−2. Let S=vi,vi+1,…,v2n−2, then ren−1∣S=ren∣S or rei∣S=ren∣S. So set S is not the basis of Fn. Hence, it is proved that edimFn=2n−1.
Note. The total number of edge resolving sets for a fan graph (Fn) is 2n.


## 3. Conclusion

In this article, the edge metric dimension for certain families of wheel-related graphs, like Jahangir graphJ2n, helm graph Hn, sunflower graph Sfn, and friendship graph Fn, have been studied and proved that all these families have unbounded edge metric dimensions. We also compared the results with their metric dimensions and concluded that dimG=edimG if G≅J2n, Hn, and dimG<edimG if G≅Sfn, Fn.


## 4. Open Problems

It is natural to ask about the characterization of the graph families on the bases of the nature of their edge metric dimension. To answer the aforementioned question, the readers are invited to study the following problems.(1)
Characterize the nanostructures, nanocones, nanotubes, nanotorus, and chemical trees on the basis of edge metric dimension.(2)
Is it the case that the other families of graphs generated by wheel also have unbounded edge metric dimension?



---

*Source: 9259032-2019-11-28.xml*