# On the Constant Edge Resolvability of Some Unicyclic and Multicyclic Graphs

Authors: Dalal Alrowaili; Zohaib Zahid; Imran Siddique; Sohail Zafar; Muhammad Ahsan; Muhammad Sarwar Sindhu
Journal: Journal of Mathematics
 (2022)

---

## Abstract

Assume thatG=VG,EG is a connected graph. For a set of vertices WE⊆VG, two edges g1,g2∈EG are distinguished by a vertex x1∈WE, if dx1,g1≠dx1,g2. WE is termed edge metric generator for G if any vertex of WE distinguishes every two arbitrarily distinct edges of graph G. Furthermore, the edge metric dimension of G, indicated by edimG, is the cardinality of the smallest WE for G. The edge metric dimensions of the dragon, kayak paddle, cycle with chord, generalized prism, and necklace graphs are calculated in this article.


---

## Body

## 1. Introduction and Preliminaries

A chemical compound’s structure is typically seen as a collection of functional groups arranged on a substructure. The structure is a labeled graph from a graph-theoretic outlook, with the vertex and edge labels indicating the atom and bond types, respectively. Functional groupings and substructure are essentially subgraphs of the labeled graph representation from this perspective. A collection of compounds described by the substructure common to them is fundamentally defined by modifying the set of functional groups and permuting their locations. Chartrand et al. defined chemistry as the application of graphs to illustrate the structure of diverse chemical compounds (see [1, 2]). We employ graph principles to explain chemical structures in chemical graph theory. Chemical compounds’ atomic structure can be presented using graphs. Johnson has worked on the application of structure-activity relationships by labeled graphs (see [3]).By establishing the concept of metric dimension, Slater was able to locate the invader in a computer network (see [4]). Harary and Melter extended the work of Slater in [5]. Hosamani et al. studied the connection to chemical problems in [6]. Berhe and Wang calculated topological coindices for nanotubes and graphene sheets in [7]. Goyal et al. focused on the new composition of graphs in [8]. Ranjini et al. investigated the applications of molecular topology by degree sequence of graph operator in [9]. Imran et al. investigated chemistry problems in order to create mathematical representations of various chemical substances, with each compound having its own representation (see [10]). Navigation can be understood within a graphical structure in which the point robot or navigating agent moves from vertex to vertex of a graph. The robot can find its location by finding the distance from a fixed set of vertices also called landmarks. There is no idea of direction and visibility in a graph, but the point robot can find the distances from a fixed set of landmarks (see [11]). Melter and Tomescu worked on the metric distances used in image processing, for example, chessboard distance and the city block distance, and they also studied the applications to pattern recognition problems (see [12]). Raza investigated the chemistry application of polyphenyl and spiro chains (see [13]). Caceres et al. described the metric dimensions of graphs in coin weighing and mastermind games (see [14]). Liu et al. worked on the application of cellular neural networks in [15]. Some applications of graphs to chemistry, biology, and physics are discussed in [16, 17]. Ali et al. studied the irregularity of graphs in detail in [18].Letw∈VG be a vertex with degree dw and the total number of edges linking to w be the degree of vertex w. G’s maximum and minimum degrees are indicated by the symbols Δ=ΔG and δ=δG, respectively. R is known as the metric generator of G if any two arbitrary elements of VG can be distinguished by some element in R⊆VG. The metric dimension of G is the number of elements in the smallest R⊆VG.Kelenc et al. [19] developed the concept of edge resolvability of graphs. The distance between edge g1 and vertex x1 is represented by dx1,g1, and it is defined as dx1,g1=mindx1,v1,dx1,v2, where g1=v1v2 (see [19]). Edges g1 and g2 are distinguished by a vertex x1 if dg1,x1≠dg2,x1. For every two distinct elements g1,g2∈EG, there always exists v1∈WE⊆VG such thatdg1,v1≠dg2,v1. The edge basis of G is thus known as the minimal WE, and WE is known as the edge metric generator. Furthermore, the minimum number of vertices in an edge basis is the edge metric dimension of G, which is denoted by edimG. A graph with only one cycle is referred to as a unicyclic graph, while a graph having more than one cycle is referred to as a multicyclic graph. We will look at both unicyclic and multicyclic graphs in this article.Kelenc et al. in [19] introduced the new concept of edim and made its comparison with metric dimension. Zubrilina in [20] calculated the n−1edim of graphs which has order n. Filipovic et al. in [21] calculated the constant value of edim of graph GPn,k for fixed values of k and computed the lower bound for the rest of the values of k. Ahsan et al. in [22] worked on the bounded and unbounded edim of some graphs. In addition, Ahsan et al. in [23] calculated the constant edim of two regular graphs. Mufti et al. in [24] computed the edimBSCayzn⊕z2 of Cayley graphs. Wei et al. calculated the edim of chordal ring network and H graph in [25]. The edim of various polyphenyl chains was determined by Ahsan et al. in [26]. Alrowaili et al. computed the edim of very important classes of Toeplitz graphs in [27]. Xing et al. compared the edge resolvability with the mixed metric of wheel graphs in [28]. Koam and Ahmad calculated the edim of barycentric subdivision of Cayley graphs in [29]. Peterin and Yero studied the edim of graph operations in [30]. Zhang and Gao calculated the edim of various graphs in [31]. Liu et al. developed the idea of fault edim of some graphs in [32]. Deng et al. computed the edim of different families of mobius networks in [33].These lemmas are helpful in determiningedim values of graphs.Lemma 1 (see [19]).
For any connected and simple graphG,(1)
1+log2δG≤edimG.(2)
log2ΔG≤edimG.Lemma 2 (see [19]).
For anyn≥2,dimPn=edimPn=1,dimCn=edimCn=2,dimKn=edimKn=n−1. Furthermore, edimG=1⟺G is path.The article is structured as follows.We will study theedim of the dragon graph Gnl, kayak paddle graph Gn,ml, cycle with chord graph Cnm, generalized prism graph Cn∗Pm, and necklace graph Nen in Sections 2, 3, 4, 5, and 6, respectively. We will discuss two classes of graphs, first one is where the usual metric dimension is equal to the edge metric dimension and the second class is where the edge dimension is greater than the usual metric dimension. The graphs have symmetry according to cycles, first graph Gnl has one cycle, second graph Gn,ml has two cycles, third graph Cnm has three cycles, and last two graphs Cn∗Pm and Nen have n cycles.


## 2. Edge Metric Dimension of Dragon GraphGnl

TheedimGnl will be computed in this section. The dragon graph Gnl has VGnl=v1,v2,…,vn,u1,u2,…,ul and EGnl=vξvξ+1:1≤ξ≤n−1∪usus+1,:1≤s≤l−1∪vnu1,u1v1. Figure 1 shows the graph Gnl for n=8 and l=6. We will look at Gnl’s metric dimension in the next theorem.Figure 1
Dragon graphG86.Theorem 1 (see [34]).
For alln≥2,l≥3,dimGnl=2.The following theorem computes theedimGnl.Theorem 2.
For alln≥2, l≥3,edimGnl=2.Proof.
We must show thatWE is an edge basis for graph Gnl if WE=v1,ul⊂VGnl. We do this by computing each edge representation of Gnl.(1)rvξvξ+1|WE=−1+ξ,l+ξ−1,if1≤ξ≤n2;ξ−1,n+l−1−ξ,ifξ=n2+1;−ξ+1+n,n+l−1−ξ,ifn2+2≤ξ≤n−1;ruξuξ+1|WE=ξ,l−ξ−1 where 1≤ξ≤l−1, rvnu1|WE=1,l−1, and ru1v1|WE=0,l−1.
We see that any two tuples are not equal. This implies thatedimGnl≤2 and now we try to show that edimGnl≥2. Since by Lemma 2, Gnl is not a path, edimGnl≥2. As a result, edimGnl=2.


## 3. Edge Metric Dimension of Kayak Paddle GraphGn,ml

TheedimGn,ml will be computed in this section. The kayak paddle graph Gn,ml has VGn,ml=u1,u2,…,vm,v1,v2,…,vn,w1,w2,…,wl and EGn,ml=vξvξ+1:1≤ξ≤n−1∪wψwψ+1:1≤ψ≤l−1∪usus+1:1≤s≤m−1∪vnw1,w1v1,wlu1,umwl. Figure 2 shows the graph Gn,ml for n = 8, m = 5, and l = 4. The metric dimension of Gn,ml is presented in the next theorem.Figure 2
Kayak paddle graphG8,54.Theorem 3 (see [35]).
Forl≥4, m≥2, and n≥2, dimGn,ml=2.The following theorem computes theedimGn,ml.Theorem 4.
Forl≥4, m≥2, and n≥2, edimGn,ml=2.Proof.
LetWE=v1,u1⊂VGn,ml, and we have to prove that WE is an edge basis for graph Gn,ml. We can do it by computing each edge representation of Gn,ml.(2)rvξvξ+1|WE=ξ−1,ξ+l,if1≤ξ≤n2,ξ−1,n+l−ξ,ifξ=n2+1,n−ξ+1,n+l−ξ,ifn2+2≤ξ≤n−1,rwξwξ+1|WE=ξ,l−ξ where 1≤ξ≤l−1.(3)ruξuξ+1|WE=l+ξ,ξ−1,if1≤ξ≤m2,m+l−ξ,ξ−1,ifξ=m2+1,m+l−ξ,m−ξ+1,ifm2+2≤ξ≤m−1.rvnw1|WE=1,l, rw1v1|WE=0,l, rwlu1|WE=l,0, and rumwl|WE=l,1.
We see that any two tuples are not equal. This implies thatedimGn,ml≤2 and now we try to prove that edimGn,ml≥2. By Lemma 2, edimGn,ml≥2. This proves that edimGn,ml=2.


## 4. Edge Metric Dimension of Cycle with Chord GraphCnm

TheedimCnm will be computed in this section. The cycle with chord graph Cnm has VCnm=a1,a2,…,an and ECnm=aξaξ+1:1≤ξ≤n−1∪ana1,a1am. It suffices to consider 2<m≤n/2. Figure 3 shows the graph Cnm for n = 16 and m = 8. We will look at Cnm’s metric dimension in the next theorem.Figure 3
Cycle with chord graphC168.Theorem 5 (see [35]).
For alln≥4, dimCnm=2.The following theorem computes theedimCnm.Theorem 6.
For alln≥4, edimCnm=2.Proof.
To calculate the edge basis ofCnm, the following are the four case scenarios.Case (i). When both numbers n and m are even. With n=2ρ and m=2ϕ and WE=aϕ+ρ,aϕ+ρ+1⊂VCnm, we must show that WE is an edge basis for graph Cnm. We do this by computing each edge representation of Cnm.(4)raξaξ+1|WE=ξ+ρ−ϕ,ξ+ρ−ϕ−1,if1≤ξ≤ϕ−1,ξ+ρ−1−ϕ,ξ+ρ−1−ϕ,ifξ=ϕ,ξ+ϕ−1+ρ,ϕ−ξ+ρ,ifϕ+1≤ξ≤ρ+ϕ−1,ξ−ϕ−ρ,ξ−ρ−ϕ,ifξ=ρ+ϕ,ξ−ρ−ϕ,ξ−1−ϕ−ρ,ifρ+ϕ+1≤ξ≤n−1.rana1|WE=n−ϕ−ρ,n−ϕ−ρ−1 and ra1am|WE=−ϕ+ρ,−ϕ+ρ.Case (ii). When the number n is odd and the number m is even. Let us say n=2ρ+1 and m=2ϕ, and let us take WE=aϕ+ρ,aϕ+ρ+2⊂VCnm. We must show that WE is an edge basis for graph Cnm. We do this by computing each edge representation of Cnm.(5)raξaξ+1|WE=ξ+ρ−ϕ,ξ+ρ−1−ϕ,if1≤ξ≤ϕ−1,ξ+ρ−ϕ−1,ξ+ρ−1−ϕ,ifξ=ϕ,−ξ+ρ+ϕ−1,ρ+ϕ−ξ,ifϕ+1≤ξ≤m−1,−ξ+ρ+ϕ−1,ρ+ϕ−ξ+1,ifm≤ξ≤ρ+ϕ−1,ξ−ρ−ϕ,ϕ+ρ+1−ξ,ifρ+ϕ≤ξ≤ρ+ϕ+1,ξ−ϕ−ρ,ξ−ϕ−2−ρ,ifρ+ϕ+2≤ξ≤n−1.rana1|WE=n−ϕ−ρ,n−ϕ−ρ−2 and ra1am|WE=−ϕ+ρ,−ϕ+ρ.Case (iii). When n is an even number and m is an odd number. Assuming n=2ρ and m=2ϕ+1, we must show that WE=aϕ+ρ,aϕ+ρ+2⊂VCnm is an edge basis for graph Cnm. We do this by computing each edge representation of Cnm.(6)raξaξ+1|WE=ξ+ρ−ϕ−1,ξ+ρ−2−ϕ,if1≤ξ≤ϕ,−ξ+ρ−1+ϕ,ξ+ρ−ϕ−2,ifξ=ϕ+1,−ξ+ρ+ϕ−1,−ξ+ρ+ϕ,ifϕ+2≤ξ≤m−1,−ξ+ρ−1+ϕ,−ξ+ϕ+ρ+1,ifm≤ξ≤ρ+ϕ−1,ξ−ϕ−ρ,−ξ+ρ+ϕ+1,ifρ+ϕ≤ξ≤ρ+ϕ+1,ξ−ρ−ϕ,ξ−ρ−ϕ−2,ifρ+ϕ+2≤ξ≤n−1.rana1|WE=n−ϕ−ρ,n−ϕ−ρ−2 and ra1am|WE=−ϕ+ρ−1,−ϕ+ρ−1.Case (iv).When both numbers n and m are odd. Assuming n=2ρ+1 and m=2ϕ+1, we must show that WE=aρ+ϕ+1,aρ+ϕ+2⊂VCnm is an edge basis for graph Cnm. We do this by computing each edge representation of Cnm.(7)raξaξ+1|WE=ξ+ρ−ϕ,ξ+ρ−ϕ−1,if1≤ξ≤ϕ,−ξ+ρ+ϕ,ξ+ρ−ϕ−1,ifξ=ϕ+1,−ξ+ρ+ϕ,−ξ+ρ+1+ϕ,ifϕ+2≤ξ≤ρ+ϕ,ξ−ρ−ϕ−1,−ξ+ρ+1+ϕ,ifξ=ρ+ϕ+1,ξ−ρ−ϕ−1,ξ−ρ−ϕ−2,ifρ+ϕ+2≤ξ≤n−1.rana1|WE=n−ϕ−ρ−1,n−ϕ−ρ−2 and ra1am|WE=−ϕ+ρ,−ϕ+ρ.
In all four case scenarios, we can observe that no two tuples have the same representations. This implies thatedimCnm≤2. Because Cnm is not a path according to Lemma 2, edimCnm≥2. As a result, edimCnm=2.


## 5. Edge Metric Dimension of Generalized Prism GraphCn∗Pm

In this part, theedimCn∗Pm will be calculated. The Cartesian product of path on m vertices and cycle on n vertices is the generalized prism graph Cn∗Pm. VCn∗Pm=aξψ:1≤ξ≤n,1≤ψ≤m and ECn∗Pm=aξψaξ+1ψ:1≤ξ≤n−1,1≤ψ≤m∪aξψaξψ+1:1≤ξ≤n,1≤ψ≤m−1∪anψa1ψ:1≤ψ≤m in the generalized prism graph Cn∗Pm. Furthermore, Cn∗P2 is referred to as a prism graph. Figure 4 shows the Cn∗Pm graph for n = 4 and m = 6. We will look at Cn∗Pm’s metric dimension in the next theorem.Figure 4
Graph ofC4∗P6.Theorem 7 (see [14]).
For alln≥3 and m≥2, we have(8)dimCn∗Pm=2,ifnis odd;3,otherwise.Lemma 3.
Forn≥2 and m≥3, edimCn∗Pm≥3.Proof.
SinceδCn∗Pm=3, by Lemma 1, we have edimCn∗Pm≥3.
In the following theorem, theedimCn∗Pm is determined.Theorem 8.
For alln≥2 and m≥3, edimCn∗Pm=3.Proof.
The following two case scenarios are used to compute the edge basis ofCn∗Pm.Case (i). When the number n is even. Let n=2k, k≥2, where k is a positive integer, and WE=a11,a21,ak+11⊂VCn∗Pm; we must show that WE is an edge basis for graph Cn∗Pm. Each edge representation of Cn∗Pm is computed for this purpose.(9)raξψaξ+1ψ|WE=ψ−1,ψ−1,n2+ψ−2,ifξ=1,1≤ψ≤m,ξ+ψ−2,ξ+ψ−3,n2−ξ+ψ−1,if2≤ξ≤n2,1≤ψ≤m,n−ξ+ψ−1,ξ+ψ−3,ξ−n2+ψ−2,ifξ=n2+1,1≤ψ≤m;n−ξ+ψ−1,n−ξ+ψ,ξ−n2+ψ−2,ifn2+2≤ξ≤n−1,1≤ψ≤m.ranψa1ψ|WE=ψ−1,ψ,ψ+n/2−2 where 1≤ψ≤m.(10)raξψaξψ+1|WE=ψ+ξ−2,ψ,n2+ψ−ξ,ifξ=1,1≤ψ≤m−1,ψ+ξ−2,ψ+ξ−3,n2+ψ−ξ,if2≤ξ≤n2+1,1≤ψ≤m−1,ψ+n−ξ,ψ+ξ−3,ψ+ξ−n2−2,ifξ=n2+2,1≤ψ≤m−1,ψ+n−ξ,ψ+n−ξ+1,ψ+ξ−n2−2,ifn2+3≤ξ≤n,1≤ψ≤m−1.Case (ii). When n is odd. Let n=2k−1, k≥2, where k is a positive integer and WE=a11,a21,ak+11⊂VCn∗Pm, and we have to prove that WE is an edge basis for graph Cn∗Pm. For this purpose, we compute each edge representation of Cn∗Pm.(11)raξψaξ+1ψ|WE=ψ−1,ψ−1,n+12+ψ−2,ifξ=1,1≤ψ≤m,ξ+ψ−2,ξ+ψ−3,n+12−ξ+ψ−1,if2≤ξ≤n+12,1≤ψ≤m,n−ξ+ψ−1,n−ξ+ψ,ξ−n+12+ψ−2,ifn+12+1≤ξ≤n−1,1≤ψ≤m.ranψa1ψ|WE=ψ−1,ψ,ψ+n+1/2−3 where 1≤ψ≤m.(12)raξψaξψ+1|WE=ψ+ξ−2,ψ,n+12+ψ−ξ−1,ifξ=1,1≤ψ≤m−1,ψ+ξ−2,ψ+ξ−3,n+12+ψ−ξ,if2≤ξ≤n+12,1≤ψ≤m−1,ψ+ξ−3,ψ+ξ−3,ψ−ξ+n+12,ifξ=n+12+1,1≤ψ≤m−1,ψ+n−ξ,ψ+n−ξ+1,ψ+ξ−n+12−2,ifn+12+2≤ξ≤n,1≤ψ≤m−1.
We see that any two tuples are not equal in both of the cases. This implies thatedimCn∗Pm≤3. Now by Lemma 3, we have edimCn∗Pm≥3. Hence, edimCn∗Pm=3.


## 6. Edge Metric Dimension of Necklace GraphNen

TheedimNen will be computed in this section. The necklace graph Nen has VNen=v0,vn+1,vφ,uφ:1≤φ≤n and ENen=vξvξ+1,uξuξ+1,uξvξ:1≤ξ≤n−1∪vnvn+1,vn+1v0,v0v1,v0u1,unvn+1,unvn. Figure 5 shows the Nen family for n=9. We will look at Nen’s metric dimension in the next theorem.Figure 5
Necklace graphNe6.Theorem 9 (see [36]).
For alln≥1, we have(13)dimNen=3,ifnis odd;2,otherwise.Lemma 4.
Forn≥2, Nen is the necklace graph family; then, edimNen≥3.Proof.
SinceδNen=3, by Lemma 1, we have edimNen≥3.
TheedimNen is computed in the following theorem.Theorem 10.
Foralln≥2, edimNen=3.Proof.
IfWE=v1,vn/2,vn⊂VNen, we must show that WE is an edge basis for graph Nen. We do this by computing each edge representation of Nen.(14)rvξvξ+1|WE=0,n2−1,2,ifξ=0,ξ−1,−ξ−1+n2,ξ+2,if1≤ξ≤n2−2,ξ−1,−ξ−1+n2,−ξ+n−1,ifξ=n2−1,ξ−1,ξ−n2,−ξ−1+n,ifn2≤ξ≤n2+1,−ξ+n+2,ξ−n2,−ξ−1+n,ifn2+2≤ξ≤n−1,−ξ+2+n,ξ−n2,ξ−n,ifξ=n,runvn+1|WE=2,n2+1,1,ruξuξ+1|WE=ξ,n2−ξ,ξ+2,if1≤ξ≤n2−2,ξ,−ξ+n2,n−ξ,ifξ=n2−1,ξ,ξ+1−n2,−ξ+n,ifξ=n2,−ξ+n+2,ξ+1−n2,−ξ+n,ifn2+1≤ξ≤n−1,rv0u1|WE=1,n2,2,ruξvξ|WE=ξ−1,n2−ξ,ξ+2,if1≤ξ≤n2−2,ξ−1,−ξ+n2,−ξ+n,ifξ=n2−1,ξ−1,ξ−n2,−ξ+n,ifn2≤ξ≤n2+1,−ξ+3+n,ξ−n2,n−ξ,ifn2+2≤ξ≤n.rvn+1v0|WE=1,n2,1.
We see that any two tuples are not equal. This implies thatedimNen≤3. Now we only prove that edimNen≥3. So, by Lemma 4, we have edimNen≥3. Hence, edimNen=3.


## 7. Conclusion

The edge metric dimension of the unicyclic and multicyclic graphs, dragon, kayak paddle, cycle with chord, generalized prism, and necklace, has been calculated in this paper. It should be underlined that the edge metric dimensions of all the described graphs are constant and do not rely on the number of vertices in the graph. The edge metric dimension of the dragon graph, kayak paddle graph, and cycle with chord graph is determined to be two, whereas the edge metric dimension of the generalized prism graph and necklace graph is determined to be three. We come to a halt here with an unsolved problem. The open problem is distinguishing between all forms of graphs in which the edge metric and metric dimensions are the same.



---

*Source: 6738129-2022-07-19.xml*