# On the Edge Metric Dimension of Certain Polyphenyl Chains

Authors: Muhammad Ahsan; Zohaib Zahid; Dalal Alrowaili; Aiyared Iampan; Imran Siddique; Sohail Zafar
Journal: Journal of Chemistry
 (2021)

---

## Abstract

The most productive application of graph theory in chemistry is the representation of molecules by the graphs, where vertices and edges of graphs are the atoms and valence bonds between a pair of atoms, respectively. For a vertexw and an edge f=c1c2 of a connected graph G, the minimum number from distances of w with c1 and c2 is called the distance between w and f. If for every two distinct edges f1,f2∈EG, there always exists w1∈WE⊆VG such that df1,w1≠df2,w1, then WE is named as an edge metric generator. The minimum number of vertices in WE is known as the edge metric dimension of G. In this paper, we calculate the edge metric dimension of ortho-polyphenyl chain graph On, meta-polyphenyl chain graph Mn, and the linear [n]-tetracene graph Tn and also find the edge metric dimension of para-polyphenyl chain graph Ln. It has been proved that the edge metric dimension of On, Mn, and Tn is bounded, while Ln is unbounded.


---

## Body

## 1. Introduction and Preliminaries

In chemical graph theory, we use the concepts of graphs to describe the chemical structures. We can present the atomic structure of chemical compounds with the help of graphs. Atoms of molecules are expressed by the vertices of the graph and bonds of atoms are denoted by the edges. Johnson represented the new technique for graphs to show the structural changes in different chemical compounds (see [1]). The idea of metric dimension in graphs was initiated by Slater to find the location of an intruder in a network (see [2]). Harary and Melter further extended the same idea in [3]. Chartrand et al. worked on the resolvability in graphs and studied the application of drug discovery in [4]. Chartrand et al. have studied the application of chemistry by representing the distinct representations of different chemical compounds on labeled graphs (see [5]). Imran et al. discussed the application of plane graphs and calculated the metric dimension of some convex polytopes in [6]. Khuller et al. studied the application of robot navigation by using fix number of landmarks as a basis (see [7]). Caceres et al. discussed the application of games like mastermind and coin weighing and further computed the Cartesian product of graphs in [8]. Melter and Tomescu studied the application of metric dimension in digitizing an image and problems of pattern recognition (see [9]). Hallaway et al. calculated the metric dimension of graph permutations in [10]. Nadeem et al. computed the metric dimension of the ortho-polyphenyl chain, meta-polyphenyl chain, and para-polyphenyl chain graphs in [11]. Soleimani et al. computed the topological indices and polynomials for a family of linear [n]-tetracene graphs in [12]. Moreover, the resolvability of graphs was calculated by Chartrand and Zhang in [13].LetG=VG,EG be a simple, connected graph. The total number of edges adjacent to vertex v1∈VG is s∈Z+, and then s is called degree of v1. ΔG and δG denote the maximum and minimum degree of G, respectively. Let x1 and x2 be two distinct vertices of G, then dx1,x2 represents the distance between them and it is defined as the number of edges in the shortest path between x1 and x2. If dx1,v1≠dx2,v1, then we say that vertex v1∈VG distinguishes x1,x2∈VG. If any two vertices of G can be distinguished by some vertex in W⊆VG, then W is called metric generator of G. The cardinality of minimum W is known as the metric dimension for G, denoted by dimG.Kelenc et al. introduced the new invariant of edge metric dimension in [14]. The distance between vertex v1 and edge e1=x1x2 is given by(1)de1,v1=mindx1,v1,dx2,v1.If for every two distinct edgese1,e2∈EG, there always exists x∈WE⊆VG such that de1,x≠de2,x, then WE is named as an edge metric generator. Minimum WE is known as the edge basis for graph G and the minimum number of vertices in WE is known as the edge metric dimension denoted by edimG. Here we represent the edge metric dimension by edim.Zubrilina showed that the ratio ofedim to usual metric is not bounded above (see [15]). Zhang and Gao computed the edim of some complex convex polytopes in [16]. Peterin and Yero calculated the edim of corona product and lexicographic of graphs in [17]. Kratica et al. worked on the edim of generalized Petersen graphs in [18]. Ahsan et al. studied the edim of circulant graphs Cn1,k for k=1 and 2 (see [19]). Yang et al. calculated the edim of some families of wheel-related graphs in [20]. Wei et al. studied the edim of some complex convex polytopes in [21]. Deng et al. computed the edim of triangular, square, and hexagonal Mobius ladder networks in [22]. Ahmad et al. calculated the edim of the benzenoid tripod structure in [23]. Furthermore, Ahsan et al. computed the edim of flower graph and prism-related graphs in [24].The following propositions are helpful throughout this article.Proposition 1 (see [14]).
For a simple, connected graphG,(1)
edimG≥1+⌈log2δG⌉(2)
edimG≥⌈log2ΔG⌉Ortho-polyphenyl chain graphOn, meta-polyphenyl chain graph Mn, and para-polyphenyl chain graph Ln under topological indices have been discussed in [25]. In the present paper, we shall discuss these polyphenyl chains under the edge metric invariant.The rest of the paper is explicit as follows. Theedim of ortho-polyphenyl chain graph On, meta-polyphenyl chain graph Mn, the linear [n]-tetracene graph Tn, and the para-polyphenyl chain graph Ln are calculated in Sections 2, 3, 4, and 5, respectively. In the last section, the conclusion of the article is stated.


## 2. Edge Metric Dimension of Ortho-Polyphenyl ChainOn

In this section, we will find theedimOn. The graph On has VOn=wi,vi,ui:1≤i≤2n and EOn=v2i+1w2i+1,w2i+1w2i+2,w2i+2v2i+2,v2i+2u2i+2,u2i+1u2i+2,v2i+1u2i+1,u2ju2j+1:0≤i≤n−1,1≤j≤n−1. The graph On for n=4 is shown in Figure 1.Figure 1
Graph of ortho-polyphenyl chainO4.Now, we will find the edge dimension of ortho-polyphenyl chainOn.Theorem 2.
Forn≥2,edimOn is 2.Proof.
LetWE=v1,u2n⊂VOn, we will prove that WE is an edge basis of On. For this, each edge of On is represented in the following:rv2i+1w2i+1|WE=0,2n,i=02+2i,2n−2i,ifn−1≥i≥1rw2i+1w2i+2|WE=1,2n,i=02i+3,2n−2i,ifn−1≥i≥1rw2i+2v2i+2|WE=2,−1+2n,i=03+2i,−2i−1+2n,ifn−1≥i≥1rv2i+1u2i+1|WE=0,2n−1,i=02i+1,−1−2i+2n,ifn−1≥i≥1ru2i+1u2i+2|WE=2i+1,2n−2i−2 for n−1≥i≥0rv2i+2u2i+2|WE=2i+2,2n−2i−2 for n−1≥i≥0ru2iu2i+1|WE=2i,−1+2n−2i for n−1≥i≥0
We see that no two tuples have the same representations. This proves thatedimOn≤2. Since by Proposition 1, edimOn≥2. Hence, edimOn=2.


## 3. Edge Metric Dimension of Meta-Polyphenyl ChainMn

In this section, we will find theedimMn. The graph Mn has VMn=wi,vi,ui:1≤i≤2n and EMn=u2i+2w2i+2,u2i+1w2i+2,v2i+1u2i+1,v2i+1w2i+1,w2i+1v2i+2,v2i+2u2i+2,u2j+2u2j+3:0≤i≤n−1,0≤j≤n−2. The graph Mn for n=5 is shown in Figure 2.Figure 2
Graph of meta-polyphenyl chainM5.Now, we will find the edge dimension of meta-polyphenyl chainMn.Theorem 3.
Forn≥2, edimMn is 2.Proof.
LetWE=w2,u2n⊂VMn, we will prove that WE is an edge basis of Mn. For this, each edge of Mn is represented in the following:ru2i+2w2i+2|WE=3i,3n−3i−4,0≤i≤n−23n−3,0,ifi=n−1ru2i+1w2i+2|WE=0,3n−3,i=03i−1,3n−3i−3,if1≤i≤n−1rv2i+1u2i+1|WE=1,n−2,i=03i−1,3n−3i−2,if1≤i≤n−1rv2i+1w2i+1|WE=2,−2+3n,ifi=03i,3n−3i−3,if1≤i≤n−1rw2i+1v2i+2|WE=2,3n−3,ifi=03i+1,3n−3i−3,if1≤i≤n−23n−2,2,ifi=n−1rv2i+2u2i+2|WE=3i+1,3n−3i−4,0≤i≤n−2−2+3n,1,ifi=n−1ru2i+2u2i+3|WE=3i+1,3n−3i−5 for 0≤i≤n−2
We see that no two tuples have the same representations. This proves thatedimMn≤2. Since by Proposition 1, edimMn≥2. Hence, edimMn=2.


## 4. Edge Metric Dimension of the Linear [n]-Tetracene

In this section, we will find theedimTn. The graph Tn has VTn=vi,ui,wj:1≤i≤5n,1≤j≤8n and ETn=v5i+1w8i+1,v5i+2w8i+3,v5i+3w8i+5,v5i+4w8i+7,w8i+1v5i+2,w8i+3v5i+3,w8i+5v5i+4,w8i+7v5i+5,v5i+2u5i+2,v5i+3u5i+3,v5i+4u5i+4,v5i+5u5i+5,u5i+2w8i+2,u5i+3w8i+4,u5i+4w8i+6,u5i+5w8i+8,u5i+1w8i+2,u5i+2w8i+4,u5i+3w8i+6,u5i+4w8i+8,v5i+1u5i+1,v5jv5j+1,u5ju5j+1:0≤i≤n−1,1≤j≤n−1. The graph Tn for n=3 is shown in Figure 3.Figure 3
Graph of the linear [3]-tetracene.We will find the edge dimension of linearn-tetracene Tn.Theorem 4.
Forn≥2, edimTn is 2.Proof.
LetWE=v1,v5n⊂VTn, we have to prove that WE is an edge basis of Tn. For this, each edge of Tn is represented in the following:rv5i+1w8i+1|WE=9i,9n−9i−2 for 0≤i≤n−1rv5i+2w8i+3|WE=9i+2,9n−9i−4 for 0≤i≤n−1rv5i+3w8i+5|WE=9i+4,9n−9i−6 for 0≤i≤n−1rv5i+4w8i+7|WE=9i+6,9n−9i−8 for 0≤i≤n−1rw8i+1v5i+2|WE=9i+1,9n−9i−3 for 0≤i≤n−1rw8i+3v5i+3|WE=9i+3,9n−9i−5 for 0≤i≤n−1rw8i+5v5i+4|WE=9i+5,9n−9i−7 for 0≤i≤n−1rw8i+7v5i+5|WE=9i+7,9n−9i−9 for 0≤i≤n−1rv5i+2u5i+2|WE=9i+2,9n−9i−3 for 0≤i≤n−1rv5i+3u5i+3|WE=9i+4,9n−9i−5 for 0≤i≤n−1rv5i+4u5i+4|WE=9i+6,9n−9i−7 for 0≤i≤n−1rv5i+5u5i+5|WE=9i+8,9n−9i−9 for 0≤i≤n−1ru5i+2w8i+2|WE=9i+2,9n−9i−2 for 0≤i≤n−1ru5i+3w8i+4|WE=9i+4,9n−9i−4 for 0≤i≤n−1ru5i+4w8i+6|WE=9i+6,9n−9i−6 for 0≤i≤n−1ru5i+5w8i+8|WE=9i+8,9n−9i−8 for 0≤i≤n−1ru5i+1w8i+2|WE=9i+1,9n−9i−1 for 0≤i≤n−1ru5i+2w8i+4|WE=9i+3,9n−9i−3 for 0≤i≤n−1ru5i+3w8i+6|WE=9i+5,9n−9i−5 for 0≤i≤n−1ru5i+4w8i+8|WE=9i+7,9n−9i−7 for 0≤i≤n−1rv5i+1u5i+1|WE=9i,9n−9i−1 for 0≤i≤n−1rv5iv5i+1|WE=9i−1,9n−9i−1 for 1≤i≤n−1;ru5iu5i+1|WE=9i,9n−9i for 1≤i≤n−1
Since every two tuples have different representations. This proves thatedimTn≤2. Since by Proposition 1, edimTn≥2. Hence, edimTn=2.


## 5. Edge Metric Dimension of Para-Polyphenyl ChainLn

In this section, we will find theedimLn. The graph Ln has VLn=vi,wi,ui:1≤i≤2n and ELn=w2i+1v2i+1,v2i+1v2i+2,v2i+2w2i+2,w2i+2u2i+2,u2i+1u2i+2,u2i+1w2i+1,w2jw2j+1:0≤i≤n−1,1≤j≤n−1. The graph Ln for n=6 is shown in Figure 4.Figure 4
Graph of para-polyphenyl chainL6.Now, we will find the edge dimension of para-polyphenyl chainLn.Lemma 5.
LetY=v1,v2,v3,…,v2n⊆VLn. Then any edge metric generator WE of Ln has at least n vertices of Y.Proof.
Suppose on contrarily thatWE has at most n−1 vertices of Y. Without loss of generality for 1≤k≤n, we assume that v2k−1,v2k∉WE, and then we have v2k−1v2k|WE=u2k−1u2k|WE, v2k−1w2k−1|WE=u2k−1w2k−1|WE, and v2kw2k|WE=u2kw2k|WE, so we get a contradiction.Remark 5.
LetWE is an edge basis of Ln. For all n, WE contains all vertices of Y having vertex indices odd.Theorem 5.
Forn≥2, we have(2)edimLn=n.Proof.
LetWE=v1,v3,v5,...,v2n−1. We will prove that WE is an edge basis of Ln.
For3≤k≤n, let W1=v1,v3,v2k−1. Now, each edge representation of Ln with respect to W1 is given in the following:(3)rw2i+1v2i+1|W1=0,4,4k−4i=0,3,0,4k−8i=1,4i−1,4i−5,4k−4i−42≤i≤k−1,4k−1,4k−5,3i=k,4i−1,4i−5,4i−4k+3k+1≤i≤n−1,rv2i+1v2i+2|W1=0,3,4k−5i=0,4i,4i−4,4k−4i−51≤i≤k−2,4k−4,4k−8,0i=k−1,4i,4i−4,4i−4k+4k≤i≤n−1.rv2i+2w2i+2|W1=1,2,−6+4ki=0,4i+1,−3+4i,−6+4k−4i1≤i≤k−2,1+4i,4i−3,4i+5−4kk−1≤i≤n−1.rw2i+2u2i+2|W1=2,2,−6+4ki=0,2+4i,4i−2,4k−4i−61≤i≤k−2,4i+2,4i−2,4i−4k+6k−1≤i≤n−1.ru2i+1u2i+2|W1=2,3,4k−5i=0,4,2,4k−9i=1,4i,4i−4,4k−4i−52≤i≤k−2,−4+4k,4k−8,2i=k−1,4i,4i−4,4i+4−4kk≤i≤n−1.ru2i+1w2i+1|W1=1,4,4k−4i=0,3,1,−8+4ki=1,−1+4i,4i−5,4k−4i−42≤i≤k−2,4k−5,4k−9,1i=k−1,−1+4i,4i−5,4i−4k+3k≤i≤n−1.rw2iw2i+1|W1=2,1,−7+4ki=1,4i−2,−8+4i,−3+4k−4i2≤i≤k−1,−2+4i,4i−6,4i+2−4kk≤i≤n−1.
From above representation we see thatv2i−1v2i|W1=u2i−1u2i|W1, v2i−1w2i−1|W1=u2i−1w2i−1|W1 and v2iw2i|W1=u2iw2i|W1 when 1≤i≤n and i≠1,2,k and no other edges have same representation. If we take 1≤i≤n and i≠1,2,k such that v2i−1v2i|W1∪v2i−1≠u2i−1u2i|W11∪v2i−1, v2i−1w2i−1|W1∪v2i−1≠u2i−1w2i−1|W1∪v2i−1 and v2iw2i|W1∪v2i−1≠u2iw2i|W1∪v2i−1. It follows that v2i−1v2i|WE≠u2i−1u2i|WE, v2i−1w2i−1|WE≠u2i−1w2i−1|WE, and v2iw2i|WE≠u2iw2i|WE for 1≤i≤n. So from Lemma 5 and Remark 5, WE is an edge basis for Ln and edimLn=n.


## 6. Conclusion

In this paper, we have calculated theedim of ortho-polyphenyl chain graph On, meta-polyphenyl chain graph Mn, linear [n]-tetracene graph Tn, and the para-polyphenyl chain graph Ln. It has been proved that the edim of these polyphenyl chain graphs is constant while the para-polyphenyl chain graph Ln has unbounded.



---

*Source: 3855172-2021-12-18.xml*