# Classes of Planar Graphs with Constant Edge Metric Dimension

Authors: Changcheng Wei; Muhammad Salman; Syed Shahzaib; Masood Ur Rehman; Juanyan Fang
Journal: Complexity
 (2021)

---

## Abstract

The number of edges in a shortest walk (without repetition of vertices) from one vertex to another vertex of a connected graphG is known as the distance between them. For a vertex x and an edge e=ab in G, the minimum number from distances of x with a and b is said to be the distance between x and e. A vertex x is said to distinguish (resolves) two distinct edges e1 and e2 if the distance between x and e1 is different from the distance between x and e2. A set X of vertices in a connected graph G is an edge metric generator for G if every two edges of G are distinguished by some vertex in X. The number of vertices in such a smallest set X is known as the edge metric dimension of G. In this article, we solve the edge metric dimension problem for certain classes of planar graphs.


---

## Body

## 1. Introduction

In graph theory, the metric dimension problem (the problem statement and its background can be found in [1–3]) captivated numerous graph theorists because of its implications in various fields, which includes discovery of networks with security and verification [4], chemistry pharmaceutics in connection with the designing of drug [1], strategies of mastermind games [5], robot navigation [6], problems of coin weighing with its solutions [7], and connected joins in graphs [8]. Due to the empirical significance of this problem, for the last two decades, many researchers have tried to solve this problem by defining several versions of the metric dimension problem such as the fractional version [9], resolving domination [10], the version of doubly metric dimension [11], independent version [12], weighted version [13], the version of k−metric dimension [14], solid version [15], mixed version [16], edge version [17], local version [18], simultaneous version [19], connected version [20], and the strong version [8].This paper is aimed to solve the edge metric dimension problem for five classes of planar graphsUn (class of convex polytopes), CRn (class of chordal ring networks), Hn (class of H-graphs), P1,n (classes of planar graph), and P2,n (classes of planar graph) by investigating their edge metric generators.


## 2. The Edge Metric Dimension

All graphs mentioned in this paper are finite, connected, undirected, and simple. Moreover, the notationsVG and EG will be used for vertex and edge sets of G, respectively. The length (number of edges) of a shortest path between two vertices a and b in G is known as the distance, da,b, between them. Let s be a vertex and e=uv be an edge in G; then, the distance between s and e is de,s=mindu,s,dv,s. The vertex s distinguishes two distinct edges e1 and e2 of G if ds,e1≠ds,e2. The metric code of an edge e with respect to a set X=x1,x2,…,xk is the k-vector:(1)cXe=de,x1,de,x2,…,de,xk.The setX is an edge metric generator for G if for every two edges e1 and e2 of G, we have cXe1≠cXe2. The cardinality of such a smallest set X for G is called the edge metric dimension of G, denoted by edimG [17].LetC be a class of connected graphs H of order k. If as H=k⟶∞,edimH≤M for some M>0, then we say that the edge metric dimension of H is bounded. Otherwise, it is unbounded. The class C of graphs is said to have a constant edge metric dimension if the edge metric dimension of graphs in the class is bounded and remains unchanged with the increase in the number of vertices of graphs.The edge metric dimension problem was introduced by Kelenc et al. in 2018 [17]. They solved this problem for cycle graphs, trees, grid graphs, and complete bipartite graphs. Moreover, examples for the relationships edimG<dimG, edimG=dimG, and edimG>dimG were also constructed by them, where the number dimG denoted the metric dimension of G [1]. Further, they explored that the determination of the edge metric dimension for a graph is an NP-complete problem. Later on, this investigation was stretched out by numerous scientists and they added to the writing with an assortment of momentous research work. For readers’ interest, we develop a short survey of results about this problem as follows:(i)
Whenever we talk about the ratioedimG/dimG between the edge metric dimension and the metric dimension of a graph G, we found an example from [17] which illustrates that this ratio is approximately equal to 5/2, but this ratio cannot be bounded above in general as proved in [21].(ii)
Graphs of ordern having the edge metric dimension n−1 are classified in [21], whereas graphs having the edge metric dimension n−2 are classified in [22].(ii)
Relationships of edge metric dimension with the maximum and minimum degrees of a graph are developed in [17, 23], while the relationship of edge metric dimension with the clique number of a graph is established in [22].(iv)
The edge metric dimension problem of various families and graph operations such as for the barycentric subdivision of Cayley graphs has been solved in [24]. Moreover, the edge metric dimension problem was solved for the join of graphs in [21, 25], for the Cartesian product of any graph G with a path Pn in [21], and for the lexicographic and corona products of graphs in [25].(v)
Further, the edge metric dimension problem has been solved for various classes of graphs, such as for necklace graphs in [26], for two classes of generalized Peterson graphs GPn,1 and GPn,2 in [23], for web graphs, convex polytope Dn, and prism-related graphs in [27], for n−sunlet graph and prism graph which turned out to be a constant in [28], for k multiwheel graphs in [29], for two classes of circulant graphs Cn1,2 and Cn1,3 in [30], and for some classes of trees, namely, stars, brooms, double brooms, and banana trees, in [31].(vi)
The edge metric dimension problem via hierarchical product and integer linear programming was discussed in [32].(vii)
Graphs having the smaller edge metric dimension than the metric dimension have been explored in [33]. Further, it has been proved that it is not possible to bound the edge metric dimension of a graph G by some constant factor of the metric dimension of G [33].(viii)
The local version of the edge metric dimension problem has been defined and studied for path graphs, ladder graphs, cycle graphs, star graphs, and wheel graphs in [34].Kelenc et al. [17] and Filipovic et al. [23] supplied the following results, which are useful tools for the investigation of the edge dimension of graphs.Proposition 1.
(see [17]). Let G be a connected graph and let ΔG be the maximum degree of G. Then, edimG≥log2ΔG.Theorem 1.
(see [23]). Let G be a connected graph and let δG be the minimum degree of G. Then, edimG≥1+log2δG.Corollary 1.
(see [23]). Let G be an r−regular graph. Then, edimG≥1+log2r.


## 3. Classes of Planar Graphs

In this section, we find the constant edge metric dimension of five classes of planar graphs, namely, family of convex polytopes, family of chordal ring networks, family ofH− graphs, and two families of particular planar graphs.


### 3.1. Class of Convex PolytopesUn

The graph of convex polytope,Un, can be constructed with the combination of the graph of a convex polytope Dn [35] and the graph of a prism Dn [36]. The half planar view of this convex polytope is shown in Figure 1. The vertex set of Un is VUn=ai,bi,ci,di,ei:1≤i≤n and the edge set is(2)EUn=aiai+1,bibi+1,eiei+1:1≤i≤n∪aibi,bici,cidi,diei,ci+1di:1≤i≤n,where the modulo n will be used when the subcript is greater than n.Figure 1
General half view ofUn in planar form.Lemma 1.
Forn=2k+1 with k≥3, the set X=a2,dk+1,e1⊆VUn is an edge metric generator.Proof.
Metric codes of the edges ofUn with respect to the set X are given as follows:(3)cXaiai+1=0,n−i−7,4,fori=1,i−2,n−i−7,i+2,for2≤i≤k,i−2,3,i+2,fori=k+1,n−i+1,i−8,n−i+4,fork+2≤i≤n,cXaibi=1,n−i+7,3,fori=1,i−2,n−i+7,i+1,for2≤i≤k+1,i−2,i−9,i+1,fori=k+2,n−i+2,i−9,n−i+4,fork+3≤i≤n,cXbibi+1=1,n−i−8,3,fori=1,i−1,n−i−8,i+1,for2≤i≤k,i−1,2,i+1,fori=k+1,i−1,i−9,n−i+3,fori=k+2,n−i+2,i−9,n−i+3,fork+3≤i≤n,cXbici=2,n−i−7,2,fori=1,i−1,n−i−7,i,for2≤i≤k,i−1,1,i,fork+1≤i≤k+2,n−i+3,i−9,n−i+3,fork+3≤i≤n,cXcidi=3,n−i−7,i,fori=1,2,n−i−7,i,fori=2,i,n−i−7,i,for3≤i≤k−1,i,2,i,fori=k,i,0,i,fori=k+1,i,1,n−i+2,fori=k+2,n−i+4,3,n−i+2,fori=k+3,n−i+4,i−8,n−i+2,fork+4≤i≤n,cXci+1di=i,n−i−6,i,for1≤i≤k−2,i,3,i,fori=k−1,i,1,i,fori=k,i,0,i,fori=k+1,i,2,n−i+2,fori=k+2,n−i+3,i−8,n−i+2,fork+3≤i≤n,cXdiei=3,n−i−8,i−1,fori=1,i+1,n−i−8,i−1,for2≤i≤k,i+1,0,i−1,fori=k+1,i+1,i−9,n−i+1,fori=k+2,n−i+4,i−9,n−i+1,fork+3≤i≤n,cXeiei+1=4,n−i−9,i−1,fori=1,i+2,n−i−9,i−1,for2≤i≤k+1,n−i+4,i−10,n−i,fork+2≤i≤n.
It can be seen that every two distinct edges ofUn have different metric codes with respect to X, which implies that X is an edge metric generator for Un.Lemma 2.
Forn=2k with k≥3, the set X=a1,a3,e1⊆VUn is an edge metric generator.Proof.
Metric codes of the edges ofUn with respect to the set X are given as follows:(4)cXaiai+1=i−1,1,4,fori=1,i−1,0,i+2,fori=2,i−1,i−3,i+2,for3≤i≤k,n−i,i−3,i+2,fori=k+1,n−i,i−3,n−i+4,fori=k+2,n−i,n−i+2,n−i+4,fork+3≤i≤n,cXaibi=i−1,2,3,fori=1,i−1,1,i+1,fori=2,i−1,i−3,i+1,for3≤i≤k+1,n−i+1,i−3,n−i+4,fork+2≤i≤k+3,n−i+1,n−i+3,n−i+4,fork+4≤i≤n,cXbibi+1=i,2,3,fori=1,i,1,i+1,fori=2,i,i−2,i+1,for3≤i≤k,n−i+1,i−2,i+1,fori=k+1,n−i+1,i−2,n−i+3,fori=k+2,n−i+1,n−i+3,n−i+3,fork+3≤i≤n,cXbici=i,3,2,fori=1,i,2,i,fori=2,i,i−2,i,for3≤i≤k+1,n−i+2,i−2,n−i+3,fork+2≤i≤k+3,n−i+2,n−i+4,n−i+3,fork+4≤i≤n,cXcidi=i+1,4,i,fori=1,i+1,3,i,fori=2,i+1,i−1,i,for3≤i≤k+1,n−i+3,i−1,n−i+2,fork+2≤i≤k+3,n−i+3,n−i+5,n−i+2,fork+4≤i≤n,cXci+1di=i+2,3,i,fori=1,i+2,i,i,for2≤i≤k,n−i+2,i,i,fori=k+1,n−i+2,i,n−i+2,fori=k+2,n−i+2,n−i+4,n−i+2,fork+3≤i≤n,cXdiei=i+2,4,i−1,fori=1,i+2,3,i−1,fori=2,i+2,i,i−1,for3≤i≤k,n−i+3,i,i−1,fori=k+1,n−i+3,i,n−i+1,fori=k+2,n−i+3,n−i+5,n−i+1,fork+3≤i≤n,cXeiei+1=i+3,4,i−1,for1≤i≤2,i+3,i+1,i−1,for3≤i≤k,n−i+4,i+1,n−i,fori=k+1,n−i+4,i+1,n−i,fori=k+2,n−i+4,n−i+5,n−i,fork+3≤i≤n.
It can be observed that for any two distinct edgese1 and e2, cXe1≠cXe2. Therefore, X is an edge metric generator for Un.Theorem 2.
For alln≥3,edimUn=3.Proof.
Note that the minimum degree inUn is δUn=3. Therefore, Theorem 2 implies that edimUn≥3. Further, Lemma 4 and Lemma 5 supply that edimUn≤3. Hence, edimUn=3.


### 3.2. Class of Chordal Ring Networks

A chord for a path in a graphG is an edge of G which joins the vertices of the path but not a part of that path. A chordal graph is an undirected graph whose every k-cycle has a chord for k≥4. In the literature, numerous types of chordal ring networks can be found, but we consider chordal ring networks supplied by Arden and Lee [37]. These chordal ring networks can be obtained by adding chords in an even order cycle in a regular way. These chords connect an even numbered vertex to an odd numbered vertex [37, 38]. Mathematically, Arden and Lee’s purposed chordal ring networks are defined as follows: let a group Zn of integers under addition module n, and let three distinct odd elements a,b, and c from Zn. Then, a chordal ring network of order n, denoted by CRna,b,c, is a graph whose vertices are labeled by the elements of Zn, and the ith labeled vertex will form an edge with the i+ath, i+bth, and i+cth labeled vertices for each even i. Accordingly, it can be seen that these chordal ring networks are cubic bipartite graphs since even numbered vertices are pairwise independent and so are the odd numbered vertices.In this section, we consider chordal ring networksCRna,b,c for a=1, b=3, and c=5, whose one graph is shown in Figure 2. For simplicity, let us divide the vertex set of CRn1,3,5 into two n/2−element sets as follows:(5)U=ui/2:fori∈Zniseven,V=vi−1/2:fori∈Znisodd.Figure 2
The chordal ring networkCR121,3,5.Accordingly, the edge set ofCRn1,3,5 should be(6)ECRn1,3,5=uivi,uivi+1,uivi+2;0≤i≤n2−1,where the modulo n/2 will be used on subscripts.In [39], it has been proved that the family of chordal ring networks CRn1,3,5 is planar whenever n=4k for k≥2. The planar drawing of this family is shown in Figure 3.Figure 3
Planar drawing ofCRn1,3,5 for n≡0mod4.It is an easy task to see that the setu0,u3,u1 is an edge metric generator for CR81,3,5. For n>8 and n=4k, we have the following result.Lemma 3.
Forn=4k with k≥3, the set X=u0,vn/2−2,u1⊆VCRn1,3,5 is an edge metric generator.Proof.
Metric codes of the edges ofCRn1,3,5 with respect to the set X are listed as follows:(7)Fori=0,cXuivi=0,i+2,0,fori=1,cXuivi=i,i+1,0,for2≤i≤k−2,cXuivi=i−1,i+2,i−1,wheni≡0mod2,i,i+1,i−2,wheni≡1mod2,fork−1≤i≤k,cXuivi=i−1,2k−i−1,i−1,wheni≡0mod2,i,2k−i−2,i−2,wheni≡1mod2,fori=k+1,cXuivi=2k−i,2k−i−1,i−1,wheni≡0mod2,2k−i+1,2k−i−2,i−2,wheni≡1mod2,fork+2≤i≤2k−2,cXuivi=2k−i,2k−i−1,2k−i+2,wheni≡0mod2,2k−i+1,2k−i−2,2k−i+1,wheni≡1mod2,fori=2k−1,cXuivi=2k−i+1,0,2k−i+1,cXuivi+1=i,i+2,1,fori=0,i,i+2,0,fori=1,i,i+2,i−1,for2≤i≤k−2,i,2k−i−2,i−1,fork−1≤i≤k,2k−i,2k−i−2,i−1,fori=k+1,2k−i,2k−i−2,2k−i+1,fork+2≤i≤2k−2,2k−i,1,2k−i+1,fori=2k−1,Fori=0,cXuivi+2=i,i+3,0,for1≤i≤k−3,cXuivi+2=i,i+3,i,wheni≡0mod2,i+1,i+2,i−1,wheni≡1mod2,fork−2≤i≤k−1,cXuivi+2=i,2k−i−2,i,wheni≡0mod2,i+1,2k−i−3,i−1,wheni≡1mod2,fori=k,cXuivi+2=2k−i−1,2k−i−2,i,wheni≡0mod2,2k−i,2k−i−3,i−1,wheni≡1mod2,fork+1≤i≤2k−3,cXuivi+2=2k−i−1,2k−i−2,2k−i+1,wheni≡0mod2,2k−i,2k−i−3,2k−i,wheni≡1mod2,for2k−2≤i≤2k−1,cXuivi+2=2k−i−1,1,2k−i+1,wheni≡0mod2,2k−i,1,2k−i,wheni≡1mod2.
It can be noticed that every two distinct edges ofCRn1,3,5 have distinct metric codes with respect to the set X. It follows that X is an edge metric generator for CRn1,3,5.Theorem 3.
Forn=4k with k≥2,edimCRn1,3,5=3.Proof.
SinceCRn1,3,5 is a 3-regular graph, so edimCRn1,3,5≥3, by Corollary 1. Further, Lemma 3 provides that edimCRn1,3,5≤3. Hence, edimCRn1,3,5=3.


### 3.3. Class ofH-Graphs

Each graph of this class is denoted byHn, which consists of n≥2 copies of H-graphs connected in a planar way as shown in Figure 4. Let the vertex set of Hn be(8)VHn=xi,yi,zi;1≤i≤2n.Figure 4
: TheH-graph H (10).Then, the edge set ofHn is(9)EHn=xixi+1,zizi+1;1≤i≤2n−1,∪xiyi,yizi;1≤i≤2n∪y2i−1y2i;1≤i≤n,∪x2nx1,z2nz1.Lemma 4.
Forn≥2, the set X=x1,x2n,z2n⊆VHn is an edge metric generator.Proof.
Metric codes of the edges ofHn with respect to the set X are given as follows:(10)cXxixi+1=i−1,i,i+2,for1≤i≤n−1,i−1,n−i+6,n−i+8,fori=n,n−i+7,n−i+6,n−i+8,forn+1≤i≤2n−1,cXx2nx1=0,0,2,cXxiyi=i−1,i,i+1,for1≤i≤n,i−1,n−i+7,n−i+8,fori=n+1,n−i+8,n−i+7,n−i+8,forn+2≤i≤2n,cXyizi=i,i+1,i,for1≤i≤n,i,n−i+8,n−i+7,fori=n+1,n−i+9,n−i+8,n−i+7,forn+2≤i≤2n,cXzizi+1=i+1,i+2,i,for1≤i≤n−1,i+1,n−i+8,n−i+6,fori=n,n−i+9,n−i+8,n−i+6,forn+1≤i≤2n−1,cXz2nz1=2,0,0,cXy2i−1y2i=2i−1,2i,2i,for1≤i≤n2,2i−1,n−2i+8,n−2i+8,fori=n2,n−2i+9,n−2i+8,n−2i+8,forn2+1≤i≤n.
It can be seen that any two different edges ofHn have different metric codes with respect to the set X, which shows that X is an edge metric generator for Hn.Theorem 4.
For alln≥2, edimHn=3.Proof.
It can be seen thatHn is a 3-regular graph. Therefore, Corollary 1 implies that edimHn≥3. Further, Lemma 4 yields that edimHn≤3. Hence, we get the required result.


### 3.4. Classes of Planar GraphP1,n and P2,n

Planar drawings of graphsP1,n and P2,n are shown in Figures 5 and 6 for n=10. For n≥3, the vertex set for both of these planar graphs has the same vertex set, which is(11)xi,yi,1≤i≤n∪zi,wi,1≤i≤n−1.Figure 5
The planar graphP1,10.Figure 6
The planar graphP2,10.But their edge sets are(12)EP1,n=xixi+1,wjwj+1,1≤i≤n−1,1≤j≤n−2,∪xiyi,zjwj,1≤i≤n,1≤j≤n−1,∪ziyi,ziyi+1,1≤i≤n−1,EP2,n=EP1,n∪yiyi+1,1≤i≤n−1.It is straightforward to see that the setx1,y3 is an edge metric generator for P1,3, which implies that edimP1,3≤2. Further, Theorem 2 provides that edimP1,3≥2 because δP1,3=2.Lemma 5.
Forn≥4, the set X=x1,yn,w1⊆VP1,n is an edge metric generator.Proof.
Metric codes of the edges ofP1,n with respect to the set X are given as follows:(13)cXxixi+1=i−1,n−i,3,fori=1,i−1,n−i,i+1,for2≤i≤n,cXxiyi=i−1,n−i+1,2,fori=1,i−1,n−i+1,i,for2≤i≤n−1,i−1,0,i,fori=n,cXyizi=i,n−i+2,i,for1≤i≤n−2,i,3,i,fori=n−1,i,1,i,fori=n,cXziyi+1=i+1,n−i+1,i,for1≤i≤n−2,i+1,2,i,fori=n−1,i+1,0,i,fori=n,cXzjwj=j+1,n−j+1,j−1,for1≤j≤n−1,j+1,1,j−1,forj=n,cXwjwj+1=j+2,n−j,j−1,for1≤j≤n.
It can be seen that every two distinct edges ofP1,n have different metric codes with respect to the set X, so X is an edge metric generator for P1,n.Lemma 6.
Forn≥4, if S is a minimum edge metric generator for P1,n, then S≥3.Proof.
AsδP1,n=2, edimP1,n=S≥2, by Theorem 2. Assume that S=2 and let S=u,v. Without loss of generality, we let u=x1. Then, S=x1,v, and we have four cases to discuss.
Wheneverv=xi for 2≤i≤n. Then,(14)For2≤i≤n−1,cSyi+1zi=i+1,2=cSziwifori=ncSzi−2yi−1=i−1,2=cSyi−1zi−1.
Wheneverv=yi for 2≤i≤n. Then,(15)For2≤i≤n−1,cSyizi−1=i,0=cSyizi,fori=ncSzi−2wi−2=i−3,3=cSwi−3wi−2.
Wheneverv=zi for 2≤i≤n−1. Then,(16)For2≤i≤n−1,cSyi+1zi=i+1,0=cSziwi.
Wheneverv=wi for 2≤i≤n−1. Then,(17)For2≤i≤n−1,cSziwi=i+1,0=cSwi−1wi.
In all these cases, we get a contradiction of the fact thatS is an edge metric generator for P1,n. Hence, our supposition is wrong and so S≥3.Theorem 5.
Forn≥4, edimP1,n=3.Proof Lemma.
5 and Lemma 6 supply the required result.Lemma 7.
Forn≥3, the set X=x1,xn,w2⊆VP2,n is an edge metric generator.Proof.
Metric codes of the edges ofP2,n with respect to the set X are given as follows:(18)cXxixi+1=i−1,n−i−1,3,for1≤i≤2,i−1,n−i−1,i,for3≤i≤n,cXxiyi=i−1,n−i,3,fori=1,i−1,n−i,2,fori=2,i−1,n−i,i−1,for3≤i≤n,cXyiyi+1=i,n−i,2,for1≤i≤2,i,n−i,i−1,for3≤i≤n,cXyizi=i,n−i+1,2,fori=1,i,n−i+1,i−1,for2≤i≤n,cXziyi+1=i+1,n−i,2,fori=1,i+1,n−i,i−1,for2≤i≤n,cXzjwj=j+1,n−j+1,1,forj=1,j+1,n−j+1,j−2,for2≤j≤n,cXwjwj+1=j+2,n−j+1,0,forj=1,j+2,n−j+1,j−2,for2≤j≤n.
It can be observed that every two distinct edges have different metric codes with respect to the setX, so X is an edge metric generator for P2,n.Theorem 8.
Forn≥3, edimP2,n=3.Proof.
Note that the maximum degree inP2,n is ΔP2,n=5. So, Proposition 1 implies that edimP2,n≥3. Further, Lemma 7 yields that edimP2,n≤3.


## 3.1. Class of Convex PolytopesUn

The graph of convex polytope,Un, can be constructed with the combination of the graph of a convex polytope Dn [35] and the graph of a prism Dn [36]. The half planar view of this convex polytope is shown in Figure 1. The vertex set of Un is VUn=ai,bi,ci,di,ei:1≤i≤n and the edge set is(2)EUn=aiai+1,bibi+1,eiei+1:1≤i≤n∪aibi,bici,cidi,diei,ci+1di:1≤i≤n,where the modulo n will be used when the subcript is greater than n.Figure 1
General half view ofUn in planar form.Lemma 1.
Forn=2k+1 with k≥3, the set X=a2,dk+1,e1⊆VUn is an edge metric generator.Proof.
Metric codes of the edges ofUn with respect to the set X are given as follows:(3)cXaiai+1=0,n−i−7,4,fori=1,i−2,n−i−7,i+2,for2≤i≤k,i−2,3,i+2,fori=k+1,n−i+1,i−8,n−i+4,fork+2≤i≤n,cXaibi=1,n−i+7,3,fori=1,i−2,n−i+7,i+1,for2≤i≤k+1,i−2,i−9,i+1,fori=k+2,n−i+2,i−9,n−i+4,fork+3≤i≤n,cXbibi+1=1,n−i−8,3,fori=1,i−1,n−i−8,i+1,for2≤i≤k,i−1,2,i+1,fori=k+1,i−1,i−9,n−i+3,fori=k+2,n−i+2,i−9,n−i+3,fork+3≤i≤n,cXbici=2,n−i−7,2,fori=1,i−1,n−i−7,i,for2≤i≤k,i−1,1,i,fork+1≤i≤k+2,n−i+3,i−9,n−i+3,fork+3≤i≤n,cXcidi=3,n−i−7,i,fori=1,2,n−i−7,i,fori=2,i,n−i−7,i,for3≤i≤k−1,i,2,i,fori=k,i,0,i,fori=k+1,i,1,n−i+2,fori=k+2,n−i+4,3,n−i+2,fori=k+3,n−i+4,i−8,n−i+2,fork+4≤i≤n,cXci+1di=i,n−i−6,i,for1≤i≤k−2,i,3,i,fori=k−1,i,1,i,fori=k,i,0,i,fori=k+1,i,2,n−i+2,fori=k+2,n−i+3,i−8,n−i+2,fork+3≤i≤n,cXdiei=3,n−i−8,i−1,fori=1,i+1,n−i−8,i−1,for2≤i≤k,i+1,0,i−1,fori=k+1,i+1,i−9,n−i+1,fori=k+2,n−i+4,i−9,n−i+1,fork+3≤i≤n,cXeiei+1=4,n−i−9,i−1,fori=1,i+2,n−i−9,i−1,for2≤i≤k+1,n−i+4,i−10,n−i,fork+2≤i≤n.
It can be seen that every two distinct edges ofUn have different metric codes with respect to X, which implies that X is an edge metric generator for Un.Lemma 2.
Forn=2k with k≥3, the set X=a1,a3,e1⊆VUn is an edge metric generator.Proof.
Metric codes of the edges ofUn with respect to the set X are given as follows:(4)cXaiai+1=i−1,1,4,fori=1,i−1,0,i+2,fori=2,i−1,i−3,i+2,for3≤i≤k,n−i,i−3,i+2,fori=k+1,n−i,i−3,n−i+4,fori=k+2,n−i,n−i+2,n−i+4,fork+3≤i≤n,cXaibi=i−1,2,3,fori=1,i−1,1,i+1,fori=2,i−1,i−3,i+1,for3≤i≤k+1,n−i+1,i−3,n−i+4,fork+2≤i≤k+3,n−i+1,n−i+3,n−i+4,fork+4≤i≤n,cXbibi+1=i,2,3,fori=1,i,1,i+1,fori=2,i,i−2,i+1,for3≤i≤k,n−i+1,i−2,i+1,fori=k+1,n−i+1,i−2,n−i+3,fori=k+2,n−i+1,n−i+3,n−i+3,fork+3≤i≤n,cXbici=i,3,2,fori=1,i,2,i,fori=2,i,i−2,i,for3≤i≤k+1,n−i+2,i−2,n−i+3,fork+2≤i≤k+3,n−i+2,n−i+4,n−i+3,fork+4≤i≤n,cXcidi=i+1,4,i,fori=1,i+1,3,i,fori=2,i+1,i−1,i,for3≤i≤k+1,n−i+3,i−1,n−i+2,fork+2≤i≤k+3,n−i+3,n−i+5,n−i+2,fork+4≤i≤n,cXci+1di=i+2,3,i,fori=1,i+2,i,i,for2≤i≤k,n−i+2,i,i,fori=k+1,n−i+2,i,n−i+2,fori=k+2,n−i+2,n−i+4,n−i+2,fork+3≤i≤n,cXdiei=i+2,4,i−1,fori=1,i+2,3,i−1,fori=2,i+2,i,i−1,for3≤i≤k,n−i+3,i,i−1,fori=k+1,n−i+3,i,n−i+1,fori=k+2,n−i+3,n−i+5,n−i+1,fork+3≤i≤n,cXeiei+1=i+3,4,i−1,for1≤i≤2,i+3,i+1,i−1,for3≤i≤k,n−i+4,i+1,n−i,fori=k+1,n−i+4,i+1,n−i,fori=k+2,n−i+4,n−i+5,n−i,fork+3≤i≤n.
It can be observed that for any two distinct edgese1 and e2, cXe1≠cXe2. Therefore, X is an edge metric generator for Un.Theorem 2.
For alln≥3,edimUn=3.Proof.
Note that the minimum degree inUn is δUn=3. Therefore, Theorem 2 implies that edimUn≥3. Further, Lemma 4 and Lemma 5 supply that edimUn≤3. Hence, edimUn=3.


## 3.2. Class of Chordal Ring Networks

A chord for a path in a graphG is an edge of G which joins the vertices of the path but not a part of that path. A chordal graph is an undirected graph whose every k-cycle has a chord for k≥4. In the literature, numerous types of chordal ring networks can be found, but we consider chordal ring networks supplied by Arden and Lee [37]. These chordal ring networks can be obtained by adding chords in an even order cycle in a regular way. These chords connect an even numbered vertex to an odd numbered vertex [37, 38]. Mathematically, Arden and Lee’s purposed chordal ring networks are defined as follows: let a group Zn of integers under addition module n, and let three distinct odd elements a,b, and c from Zn. Then, a chordal ring network of order n, denoted by CRna,b,c, is a graph whose vertices are labeled by the elements of Zn, and the ith labeled vertex will form an edge with the i+ath, i+bth, and i+cth labeled vertices for each even i. Accordingly, it can be seen that these chordal ring networks are cubic bipartite graphs since even numbered vertices are pairwise independent and so are the odd numbered vertices.In this section, we consider chordal ring networksCRna,b,c for a=1, b=3, and c=5, whose one graph is shown in Figure 2. For simplicity, let us divide the vertex set of CRn1,3,5 into two n/2−element sets as follows:(5)U=ui/2:fori∈Zniseven,V=vi−1/2:fori∈Znisodd.Figure 2
The chordal ring networkCR121,3,5.Accordingly, the edge set ofCRn1,3,5 should be(6)ECRn1,3,5=uivi,uivi+1,uivi+2;0≤i≤n2−1,where the modulo n/2 will be used on subscripts.In [39], it has been proved that the family of chordal ring networks CRn1,3,5 is planar whenever n=4k for k≥2. The planar drawing of this family is shown in Figure 3.Figure 3
Planar drawing ofCRn1,3,5 for n≡0mod4.It is an easy task to see that the setu0,u3,u1 is an edge metric generator for CR81,3,5. For n>8 and n=4k, we have the following result.Lemma 3.
Forn=4k with k≥3, the set X=u0,vn/2−2,u1⊆VCRn1,3,5 is an edge metric generator.Proof.
Metric codes of the edges ofCRn1,3,5 with respect to the set X are listed as follows:(7)Fori=0,cXuivi=0,i+2,0,fori=1,cXuivi=i,i+1,0,for2≤i≤k−2,cXuivi=i−1,i+2,i−1,wheni≡0mod2,i,i+1,i−2,wheni≡1mod2,fork−1≤i≤k,cXuivi=i−1,2k−i−1,i−1,wheni≡0mod2,i,2k−i−2,i−2,wheni≡1mod2,fori=k+1,cXuivi=2k−i,2k−i−1,i−1,wheni≡0mod2,2k−i+1,2k−i−2,i−2,wheni≡1mod2,fork+2≤i≤2k−2,cXuivi=2k−i,2k−i−1,2k−i+2,wheni≡0mod2,2k−i+1,2k−i−2,2k−i+1,wheni≡1mod2,fori=2k−1,cXuivi=2k−i+1,0,2k−i+1,cXuivi+1=i,i+2,1,fori=0,i,i+2,0,fori=1,i,i+2,i−1,for2≤i≤k−2,i,2k−i−2,i−1,fork−1≤i≤k,2k−i,2k−i−2,i−1,fori=k+1,2k−i,2k−i−2,2k−i+1,fork+2≤i≤2k−2,2k−i,1,2k−i+1,fori=2k−1,Fori=0,cXuivi+2=i,i+3,0,for1≤i≤k−3,cXuivi+2=i,i+3,i,wheni≡0mod2,i+1,i+2,i−1,wheni≡1mod2,fork−2≤i≤k−1,cXuivi+2=i,2k−i−2,i,wheni≡0mod2,i+1,2k−i−3,i−1,wheni≡1mod2,fori=k,cXuivi+2=2k−i−1,2k−i−2,i,wheni≡0mod2,2k−i,2k−i−3,i−1,wheni≡1mod2,fork+1≤i≤2k−3,cXuivi+2=2k−i−1,2k−i−2,2k−i+1,wheni≡0mod2,2k−i,2k−i−3,2k−i,wheni≡1mod2,for2k−2≤i≤2k−1,cXuivi+2=2k−i−1,1,2k−i+1,wheni≡0mod2,2k−i,1,2k−i,wheni≡1mod2.
It can be noticed that every two distinct edges ofCRn1,3,5 have distinct metric codes with respect to the set X. It follows that X is an edge metric generator for CRn1,3,5.Theorem 3.
Forn=4k with k≥2,edimCRn1,3,5=3.Proof.
SinceCRn1,3,5 is a 3-regular graph, so edimCRn1,3,5≥3, by Corollary 1. Further, Lemma 3 provides that edimCRn1,3,5≤3. Hence, edimCRn1,3,5=3.


## 3.3. Class ofH-Graphs

Each graph of this class is denoted byHn, which consists of n≥2 copies of H-graphs connected in a planar way as shown in Figure 4. Let the vertex set of Hn be(8)VHn=xi,yi,zi;1≤i≤2n.Figure 4
: TheH-graph H (10).Then, the edge set ofHn is(9)EHn=xixi+1,zizi+1;1≤i≤2n−1,∪xiyi,yizi;1≤i≤2n∪y2i−1y2i;1≤i≤n,∪x2nx1,z2nz1.Lemma 4.
Forn≥2, the set X=x1,x2n,z2n⊆VHn is an edge metric generator.Proof.
Metric codes of the edges ofHn with respect to the set X are given as follows:(10)cXxixi+1=i−1,i,i+2,for1≤i≤n−1,i−1,n−i+6,n−i+8,fori=n,n−i+7,n−i+6,n−i+8,forn+1≤i≤2n−1,cXx2nx1=0,0,2,cXxiyi=i−1,i,i+1,for1≤i≤n,i−1,n−i+7,n−i+8,fori=n+1,n−i+8,n−i+7,n−i+8,forn+2≤i≤2n,cXyizi=i,i+1,i,for1≤i≤n,i,n−i+8,n−i+7,fori=n+1,n−i+9,n−i+8,n−i+7,forn+2≤i≤2n,cXzizi+1=i+1,i+2,i,for1≤i≤n−1,i+1,n−i+8,n−i+6,fori=n,n−i+9,n−i+8,n−i+6,forn+1≤i≤2n−1,cXz2nz1=2,0,0,cXy2i−1y2i=2i−1,2i,2i,for1≤i≤n2,2i−1,n−2i+8,n−2i+8,fori=n2,n−2i+9,n−2i+8,n−2i+8,forn2+1≤i≤n.
It can be seen that any two different edges ofHn have different metric codes with respect to the set X, which shows that X is an edge metric generator for Hn.Theorem 4.
For alln≥2, edimHn=3.Proof.
It can be seen thatHn is a 3-regular graph. Therefore, Corollary 1 implies that edimHn≥3. Further, Lemma 4 yields that edimHn≤3. Hence, we get the required result.


## 3.4. Classes of Planar GraphP1,n and P2,n

Planar drawings of graphsP1,n and P2,n are shown in Figures 5 and 6 for n=10. For n≥3, the vertex set for both of these planar graphs has the same vertex set, which is(11)xi,yi,1≤i≤n∪zi,wi,1≤i≤n−1.Figure 5
The planar graphP1,10.Figure 6
The planar graphP2,10.But their edge sets are(12)EP1,n=xixi+1,wjwj+1,1≤i≤n−1,1≤j≤n−2,∪xiyi,zjwj,1≤i≤n,1≤j≤n−1,∪ziyi,ziyi+1,1≤i≤n−1,EP2,n=EP1,n∪yiyi+1,1≤i≤n−1.It is straightforward to see that the setx1,y3 is an edge metric generator for P1,3, which implies that edimP1,3≤2. Further, Theorem 2 provides that edimP1,3≥2 because δP1,3=2.Lemma 5.
Forn≥4, the set X=x1,yn,w1⊆VP1,n is an edge metric generator.Proof.
Metric codes of the edges ofP1,n with respect to the set X are given as follows:(13)cXxixi+1=i−1,n−i,3,fori=1,i−1,n−i,i+1,for2≤i≤n,cXxiyi=i−1,n−i+1,2,fori=1,i−1,n−i+1,i,for2≤i≤n−1,i−1,0,i,fori=n,cXyizi=i,n−i+2,i,for1≤i≤n−2,i,3,i,fori=n−1,i,1,i,fori=n,cXziyi+1=i+1,n−i+1,i,for1≤i≤n−2,i+1,2,i,fori=n−1,i+1,0,i,fori=n,cXzjwj=j+1,n−j+1,j−1,for1≤j≤n−1,j+1,1,j−1,forj=n,cXwjwj+1=j+2,n−j,j−1,for1≤j≤n.
It can be seen that every two distinct edges ofP1,n have different metric codes with respect to the set X, so X is an edge metric generator for P1,n.Lemma 6.
Forn≥4, if S is a minimum edge metric generator for P1,n, then S≥3.Proof.
AsδP1,n=2, edimP1,n=S≥2, by Theorem 2. Assume that S=2 and let S=u,v. Without loss of generality, we let u=x1. Then, S=x1,v, and we have four cases to discuss.
Wheneverv=xi for 2≤i≤n. Then,(14)For2≤i≤n−1,cSyi+1zi=i+1,2=cSziwifori=ncSzi−2yi−1=i−1,2=cSyi−1zi−1.
Wheneverv=yi for 2≤i≤n. Then,(15)For2≤i≤n−1,cSyizi−1=i,0=cSyizi,fori=ncSzi−2wi−2=i−3,3=cSwi−3wi−2.
Wheneverv=zi for 2≤i≤n−1. Then,(16)For2≤i≤n−1,cSyi+1zi=i+1,0=cSziwi.
Wheneverv=wi for 2≤i≤n−1. Then,(17)For2≤i≤n−1,cSziwi=i+1,0=cSwi−1wi.
In all these cases, we get a contradiction of the fact thatS is an edge metric generator for P1,n. Hence, our supposition is wrong and so S≥3.Theorem 5.
Forn≥4, edimP1,n=3.Proof Lemma.
5 and Lemma 6 supply the required result.Lemma 7.
Forn≥3, the set X=x1,xn,w2⊆VP2,n is an edge metric generator.Proof.
Metric codes of the edges ofP2,n with respect to the set X are given as follows:(18)cXxixi+1=i−1,n−i−1,3,for1≤i≤2,i−1,n−i−1,i,for3≤i≤n,cXxiyi=i−1,n−i,3,fori=1,i−1,n−i,2,fori=2,i−1,n−i,i−1,for3≤i≤n,cXyiyi+1=i,n−i,2,for1≤i≤2,i,n−i,i−1,for3≤i≤n,cXyizi=i,n−i+1,2,fori=1,i,n−i+1,i−1,for2≤i≤n,cXziyi+1=i+1,n−i,2,fori=1,i+1,n−i,i−1,for2≤i≤n,cXzjwj=j+1,n−j+1,1,forj=1,j+1,n−j+1,j−2,for2≤j≤n,cXwjwj+1=j+2,n−j+1,0,forj=1,j+2,n−j+1,j−2,for2≤j≤n.
It can be observed that every two distinct edges have different metric codes with respect to the setX, so X is an edge metric generator for P2,n.Theorem 8.
Forn≥3, edimP2,n=3.Proof.
Note that the maximum degree inP2,n is ΔP2,n=5. So, Proposition 1 implies that edimP2,n≥3. Further, Lemma 7 yields that edimP2,n≤3.


## 4. Conclusion

With this article, we have extended the study of the edge metric dimension problem towards few classes of planar graphs. We observed that in each of the considered classes of planar graphs, the edge metric dimension is not changed when we increase the number of vertices in graphs, which yields that the investigated edge metric dimension is constant. In fact, we proved that only three vertices are sufficient to distinguish (resolve) every pair of edges in each planar graph of the considered classes [40–44].



---

*Source: 5599274-2021-04-05.xml*