# A Comparative Study of Three Resolving Parameters of Graphs

Authors: Hafiz Muhammad Ikhlaq; Hafiz Muhammad Afzal Siddiqui; Muhammad Imran
Journal: Complexity
 (2021)

---

## Abstract

Graph theory is one of those subjects that is a vital part of the digital world. It is used to monitor the movement of robots on a network, to debug computer networks, to develop algorithms, and to analyze the structural properties of chemical structures, among other things. It is also useful in airplane scheduling and the study of diffusion mechanisms. The parameters computed in this article are very useful in pattern recognition and image processing. A numberdf,w=mindw,t,dw,s is referred as distance between f=ts an edge and w a vertex. dw,f1≠dw,f2 implies that two edges f1,f2∈E are resolved by node w∈V. A set of nodes A is referred to as an edge metric generator if every two links/edges of Γ are resolved by some nodes of A and least cardinality of such sets is termed as edge metric dimension, edimΓ for a graph Γ. A set B of some nodes of Γ is a mixed metric generator if any two members of V∪E are resolved by some members of B. Such a set B with least cardinality is termed as mixed metric dimension, mdimΓ. In this paper, the metric dimension, edge metric dimension, and mixed metric dimension of dragon graph Tn,m, line graph of dragon graph LTn,m, paraline graph of dragon graph LSTn,m, and line graph of line graph of dragon graph LLTn,m have been computed. It is shown that these parameters are constant, and a comparative analysis is also given for the said families of graphs.


---

## Body

## 1. Introduction

For several years, the characteristics associated to graph distances have piqued the interest of various scholars, and one of them, the metric dimension, has recently been the focus of them. The theory of metric dimension was given by Slater in 1975 [1] and this theory was further elaborated as resolving set of graphs by Harary and Melter in 1976 [2]. In 2003, Brigham et al. [3] determined resolving dominating set and resolving domination number in graphs. In 2003, Chartrand et al. [4] studied the independent resolving set in nontrivial connected graphs of order n. The order of minimal independent resolving set is known as independent resolving number and is denoted as irΓ. In 2003, Saenpholphat and Zhang [5] calculated the connected resolving number of complete graph Kn, star graph K1,n−1, and Cartesian products of Γ×K2. In 2007, Oellermann and Peters-Fransen [6] found the strong metric dimension of graphs and digraphs. In 2010, Okamoto et al. [7] discussed the local metric dimension of graphs and some bounds of it. In 2017, Yero et al. [8] determined the k-metric dimensional graphs. In 2016, Imran and Siddiqui [9] computed the metric dimension of some convex polytopes generated by wheel related graphs. A graph in which all vertices have the same degree is called a regular graph. Ali presented a survey of antiregular graphs [10], and he gathered the known results concerning the antiregular graphs.There are many applications of this parameter to robot navigation in networks which have been discussed in [11] and applications to chemistry have been discussed in [4, 12]. Furthermore, this issue has certain applications to pattern recognition and image processing difficulties, some of which require the usage of hierarchical data structures [13]. Some interesting connections between metric generators in graphs and the master mind game or coin weighing have been presented in [14]. The metric dimension of infinite graphs was studied in [15], and extremal graphs for metric dimension and diameter were considered in [16].LetΓ be a simple connected and undirected graph with the vertex set VΓ and edge set EΓ. The distance between any two vertices u,v∈VΓ is denoted as du,v and is defined as the length of the shortest path between u and v. The vertex t resolves the vertices uandv if dt,u≠dt,v. An ordered set of i vertices R=x1,x2,…,xi; the identification of x depending on R is the order i− tuple and is written as(1)ru|R=dx,x1,dx,x2,dx,x3,…,dx,xi.If the different vertices ofΓ have different codes based on R, then R is known as a resolving set for Γ. Let Ω⊂Γ of graph Γ be such that Ω=minR:R is a resolving set forΓ, then Ω is a metric basis for the graph Γ and dimΓ=Ω is metric dimension of the graph Γ.Recently, the idea of edge metric dimension of graphedimΓ was given by Kelenc et al. [17], and they also presented some results and comparison of metric dimension and edge metric dimension for some well-known families of graphs like path graph Pn, edimPn=dimPn=1 where n is number of vertices of graph, cycle graph Cn: edimCn=dimCn=2, complete graph Kn: edimKn=dimKn=n−1, and complete bipartite graph Kr,t: edimKr,t=dimKr,t=r+t−2, where r,t>1 are vertices of each partite set; if Γ is a grid graph Γ=Pr×Pt with r≥t≥2, then edimΓ=2. Furthermore, they have raised many open problems linked to the nature of metric dimension and edge metric dimension. In 2018, Liu et al. [18] worked on edge version of metric dimension and calculated edge metric dimension of necklace graph and line graph of necklace graph. In 2021, Deng et al. [19] discussed the edge resolvability parameter for different families of Mobius ladder networks, and they find the exact edge metric dimension of triangular, square, and hexagonal Mobius ladder networks.The distance between an edgee=tp and a vertex q is denoted as de,q and is defined as de,q=mindt,q,dp,q. The vertex u resolves the edges eiandel if dei,u≠del,u. An ordered set of j vertices A=a1,a2,…,aj; the identification of an edge eα depending on A is the order j− tuple and is written as(2)reα|A=deα,a1,deα,a2,deα,a3,…,deα,aj.If the different edges ofΓ have different codes based on A, then A is known as an edge resolving set for Γ. Let L be a subset of vertex set of graph Γ such that |L|=min|L|:Lis an edge resolving set forΓ, then L is an edge metric basis for the graph Γ and edimΓ=L is edge metric dimension of the graph Γ.Kelenc et al. [20] has presented the idea of mixed metric dimension and denoted it as mdimΓ, and they presented the mixed metric dimension of path graph Pn, mdimPn=2, cycle graph Cn, mdimCn=3, and complete bipartite graph Kr,t, mdimKr,t=r+t−1 where r,t=2; otherwise, mdimKr,t=r+t−2 and grid graph Γ=Pr□Pt, mdimΓ=3 where r≥t≥2. An ordered subset of a vertex set of a graph is called mixed resolving set if it is both vertex resolving set and edge resolving set. Let Γ be a graph and X=x1,x2,…,xk be an ordered subset of vertices of graph Γ. If all vertices and edges of Γ have different codes of representation with respect to the set X, then X is known as a mixed resolving set for graph Γ. Let M be a subset of vertex set of graph Γ such that M=min:Xis a mixed resolving set for graphΓ. Then, M is known as a mixed metric basis for Γ, and mdimΓ=M is a mixed metric dimension of the graph Γ. In 2016, Yero [21] presented some bounds or closed formulae for the (edge, mixed) metric dimension of several families of graphs.Figure1 represents graph Γ with VΓ=v1,v2,…,v8, and EΓ=a,b,c,d,e,f,g,h are vertex set and edge set, respectively. The set A=v2,v7 is an edge resolving set of Γ. The representation of all edges with respect to A is as given in Table 1.Figure 1
A graph with theedimΓ=2.Table 1
Edge distance codes ofΓ w.r.t. A.
d.,.abcdA=v2,v70,10,21,32,3d.,.efghA=v2,v72,21,11,02,4All edges have different representations with respect toA, so edimΓ=2.The setB=v2,v7,v8 is a mixed resolving set of Γ. The representation of all edges and vertices with respect to B is as given in Table 2.Table 2
Mixed distance codes ofΓ w.r.t. B.
d.,.abcdB=v2,v7,v80,1,30,2,21,3,12,3,1d.,.efghB=v2,v7,v82,2,21,1,31,0,42,4,0d.,.v1v2v3v4B=v2,v7,v81,1,40,2,31,3,22,4,1d.,.v5v6v7v8B=v2,v7,v83,3,22,2,31,1,42,0,5All edges and vertices have different representations with respect toB, so mdimΓ=3.Theorem 1 (see [12]).
A connected graphΓ of order n has dimension 1 if and only if Γ=Pn.Theorem 2 (see [22]).
LetTn,m be a dragon graph for n≥3 and m≥2. Then, dimTn,m=2.Theorem 3 (see [17]).
The edge metric dimension of a graphG is 1 if and only if Γ is a path.Theorem 4 (see [20]).
The mixed metric dimension of a graphG is 2 if and only if Γ is a path.


## 2. Results on Dragon GraphTn,m

Dragon graph is obtained by identifying vertexvn of cycle graph Cn with vertex u0 of path graph Pm+1 and is denoted as Tn,m. Order of dragon graph Tn,m is n+m. Its vertex set is VTn,m=v1,v2,…,vn,u1,u2,…,um and edge set is ETn,m=vivi+1:1≤i≤n∪ujuj+11≤j≤m−1∪vnu1 where vn+1=v1 as shown in Figure 2.Figure 2
Dragon graphT8,5.Theorem 5.
LetTn,m be a dragon graph for n≥3 and m≥2. Then, edimTn,m=2.Proof.
Since dragon graph is not a path graph,edimTn,m≥2. In this case, A=v1,um is an edge resolving set of Tn,m. All edges are labeled as(3)ei=vivi+1:1≤i≤n,ej+1′=ujuj+1:1≤j≤m−1,e1′=vnu1.
The representations of all edges with respect toA are as follows:(4)rei|A=i−1,m+i1≤i≤n2−1;i−1,m+n−i−1i=n2;n−i,m+n−i−1n2+1≤i≤n−1;0,mi=n.rej′|A=j,m−j:1≤j≤m.
All edges have distinguished representation, and this fact can easily be verified, which implies thatedimTn,m≤2. So, we obtained edimTn,m=2.Theorem 6.
LetTn,m be a dragon graph for n≥3 and m≥2. Then, mdimTn,m=3.Proof.
Since dragon graph is not a path graph,mdimTn,m≥3. All edges are labeled as(5)ei=vivi+1:1≤i≤n,ej+1′=ujuj+1:1≤j≤m−1,e1′=vnu1.
In this case,A=v1,v⌈n/2⌉,um is mixed resolving set of Tn,m. The representations of all vertices with respect to A are as follows:(6)ruj|A=j+1,n2+j,m−j:1≤j≤m.
Forn even,(7)rvi|A=i−1,n2−i,m+i1≤i≤n2;n−i+1,i−n2,m+n−in2+1≤i≤n.
Forn odd,(8)rvi|A=i−1,n2−i,m+i1≤i≤n2;i−1,n2−i,m+n−ii=n2+1;n−i+1,i−n2,m+n−in2+2≤i≤n.
The representations of all edges with respect toA are as follows:(9)rej′|A=j,n2+j−1,m−j:1≤j≤m.
Forn even,(10)rei|A=i−1,n2−i−1,m+i1≤i≤n2−1;i−1,i−n2,m+n−i−1i=n2;n−i,i−n2,m+n−i−1n2+1≤i≤n−1;0,n2−1,mi=n.
Forn odd,(11)rei|A=i−1,n2−i−1,m+i1≤i≤n2−1;i−1,n2−i−1,m+n−i−1i=n2;n−i,i−n2,m+n−i−1n2+1≤i≤n−1;0,n2−1,mi=n.
From the above representation, it is clear that no two vertices, edges, and an edge or a vertex ofTn,m have the same representation which implies that mdimTn,m≤3. So, we obtained mdimTn,m=3.


## 3. Results on Line Graph of Dragon GraphLTn,m

A line graphLΓ of Γ can be generated by assuming edge set of Γ as vertex set of LΓ, and any two vertices of LΓ are adjacent if and only if they are neighboring edges in Γ. Line graph of dragon graph has VLTn,m=a1,a2,…,an,b1,b2,…,bm and ELTn,m=ai,ai+1,bjbj+1:1≤i≤n,1≤j≤m−1∪a1b1,anb1 as its set of vertices and set of edges, where an+1=a1 as shown in Figure 3.Figure 3
Line graph of dragon graphLT8,5.Theorem 7.
LetLTn,m be a line graph of dragon graph for n≥3 and m≥2. Then, dimLTn,m=2.Proof.
SincedimLTn,m≥2, it is not a path graph Pn. A=a2,bm is resolving set of LTn,m, and the representations of all vertices with respect to A are as follows:(12)rai|A=1,m,i=1;i−2,m+i−12≤i≤n2;i−2,n+m−ii=n2+1;n−i+2,n+m−in2+2≤i≤n.rbj|A=j+1,m−j:1≤j≤m.
All vertices have different representation, which implies thatdimLTn,m≤2. So, we obtained dimLTn,m=2.Theorem 8.
LetLTn,m be a line graph of dragon graph for n≥3 and m≥2. Then, edimLTn,m=2.Proof.
SinceedimLTn,m≥2, it is not a path graph Pn. All edges of LTn,m are labeled as e1′=a1b1 and e0′=anb1.
ei=aiai+1:1≤i≤n and ej+1′=bjbj+1:1≤j≤m−1.
A=a2,bm is an edge resolving set of LTn,m, and representations of all edges with respect to A are as follows:(13)re0′|A=2,m−1,rej′|A=j,m−j:1≤j≤m,rei|A=0,m+i−1i=1;i−2,m+i−12≤i≤n2;i−2,m+n−i−1i=n2+1;n−i+1,m+n−i−1n2+2≤i≤n−1;n−i+1,mi=n.
All edges have different representation, which implies thatedimLTn,m≤2. So, we obtained edimLTn,m=2.Theorem 9.
LetLTn,m be a line graph of dragon graph for n≥3 and m≥1. Then, mdimLTn,m=3.Proof.
SincemdimLTn,m≥3, it is not a path graph Pn. All edges of LTn,m are labeled as(14)en=a1an,e1′=a1b1,e0′=anb1.
ei=aiai+1:1≤i≤n−1 and ej+1′=bjbj+1:1≤j≤m−1.
A=a2,a⌊n/2⌋+1,bm is mixed resolving set of LTn,m, and the representations of all edges with respect to A are as follows:(15)rei|A=0,n2−i,m+i−1i=1;i−2,n2−i,m+i−12≤i≤n2;i−2,i−n2−1,m+n−i−1i=n2+1;n−i+1,i−n2−1,m+n−i−1n2+2≤i≤n−1;n−i+1,i−n2−1,mi=n.
Forn even,(16)rej′|A=j,n2,m−j:j=1;j,n2+j−2,m−j:2≤j≤m,re0′|A=2,n2−1,m−1.
Forn odd,(17)rej′|A=j,n2+j−1,m−j:1≤j≤m,re0′|A=2,n2,m−1.
The representations of all vertices with respect toA are as follows:(18)rap|A=1,n2+1−p,m+p−1p=1;p−2,n2+1−p,m+p−12≤p≤n2;p−2,p−n2−1,m+n−pp=n2+1;n−p+2,p−n2−1,m+n−pn2+2≤p≤n.rbq|A=q+1,n2+q−1,m−q:1≤q≤m.
From the above representation, it is clear that no two vertices, edges, and an edge or a vertex ofLTn,m have the same representation which implies that mdimLTn,m≤3. So, we obtained mdimLTn,m=3.


## 4. Results on Paraline Graph of Dragon GraphLSTn,m

Paraline graph is the line graph of the subdivision graph of any graph. In subdivision graphS=SΓ, the vertex set is VS=VΓ∪EΓ and the vertex of S corresponding to the edge uv of Γ is inserted in the edge uv of Γ. In line graph L=LΓ, the vertex set is VL=EG and two vertices of L are adjacent if the corresponding edges of Γ are incident. Paraline graph of dragon graph has VLSTn,m=a1,a2,…,a2n,b1,b2,…,b2m and ELSTn,m=ai,ai+1,bjbj+1:1≤i≤2n,1≤j≤2m−1∪a1b1,a2nb1 as its set of vertices and set of edges, where a2n+1=a1 as shown in Figure 4.Figure 4
(a) Dragon graphT4,2; (b) Subdivision graph of dragon graph ST4,2; (c) Paraline graph of dragon graph LST4,2.
(a)(b)(c)Theorem 10.
LetLSTn,m be a paraline graph of dragon graph for n≥3 and m≥2. Then, dimLSTn,m=2.Proof.
SincedimLSTn,m≥2, it is not a path graph Pn. A=a2,b2m is resolving set of LSTn,m, and the representations of all vertices with respect to A are(19)rai|A=1,2m,i=1;i−2,2m+i−12≤i≤n;i−2,2n+m−ii=n+1;2n−i+2,2n+m−in+2≤i≤2n,rbj|A=j+1,2m−j:1≤j≤2m.
All vertices have different representation, and this fact can easily be verified, which implies thatdimLSTn,m≤2. So, we obtained dimLSTn,m=2.Theorem 11.
LetLSTn,m be a paraline graph of dragon graph for n≥3 and m≥2. Then, edimLSTn,m=2.Proof.
SinceedimLSTn,m≥2, it is not a path graph Pn. All edges of LSTn,m are labeled as e1′=a1b1 and e0′=a2nb1.
ei=aiai+1:1≤i≤2n and ej+1′=bjbj+1:1≤j≤2m−1.
A=a2,b2m is an edge resolving set of LSTn,m, and representations of all edges with respect to A are as follows:(20)re0′|A=2,2m−1,rej′|A=j,2m−j:1≤j≤m,rei|A=0,2m+i−1i=1;i−2,2m+i−12≤i≤n;i−2,2m+n−i−1i=n+1;2n−i+1,2m+n−i−1n+2≤i≤2n−1;2n−i+1,2mi=2n.
All edges have different representation, which implies thatedimLSTn,m≤2. So, we obtained edimLSTn,m=2.Theorem 12.
LetLSTn,m be a paraline graph of dragon graph for n≥3 and m≥1. Then, mdimLSTn,m=3.Proof.
SincemdimLSTn,m≥3, it is not a path graph Pn. All edges of LSTn,m are labeled as(21)e2n=a1a2n,e1′=a1b1,e0′=a2nb1.
ei=aiai+1:1≤i≤2n−1 and ej+1′=bjbj+1:1≤j≤2m−1.
A=a2,an+1,b2m is mixed resolving set of LSTn,m, and the representations of all edges with respect to A are as follows:(22)rei|A=0,n−i,2m+i−1i=1;i−2,n−i,2m+i−12≤i≤n;i−2,i−n−1,2m+n−i−1i=n+1;2n−i+1,i−n−1,2m+n−i−1n+2≤i≤2n−1;2n−i+1,i−n−1,2mi=2n.rej′|A=2,n2−1,m−1j=0;j,n,2m−jj=1;j,n+j−2,2m−j2≤j≤2m.
The representations of all vertices with respect toA are as follows:(23)rap|A=1,n+1−p,2m+p−1p=1;p−2,n+1−p,2m+p−12≤p≤n;p−2,p−n−1,2m+n−pp=n+1;2n−p+2,p−n−1,2m+n−pn+2≤p≤2n,rbq|A=q+1,n+q−1,2m−q:1≤q≤2m.
From the above representation, it is clear that no two vertices, edges, and an edge or a vertex ofLSTn,m have the same representation which implies that mdimLSTn,m≤3. So, we obtained mdimLSTn,m=3.


## 5. Results on Line Graph of Dragon GraphLLTn,m

LetΓ be a graph and LLTn,m be line graph of line graph of dragon graph Tn.m. Vertex set of line graph of line graph of dragon graph is VLLTn,m=a1,a2,…,an,b0,b1,b2,…,bm−1, and its edge set is ELTn,m=ai,ai+1,bjbj+1:1≤i≤n,0≤j≤m−2∪an−1b0,anb0,anb1,a1b1,b0b2 where an+1=a1 as shown in Figure 5.Figure 5
Paraline graph of dragon graphLLT8,5.Theorem 13.
LetLLTn,m be a line graph of line graph of dragon graph for n≥3 and m≥3. Then, dimLLTn,m=2.Proof.
SincedimLLTn,m≥2, it is not a path graph Pn. A=a2,bm−1 is resolving set of LLTn,m, and the representations of all vertices with respect to A are as follows:(24)rbj|A=3,m−2j=0;j+1,m−j−11≤j≤m−1.
Forn even,(25)rai|A=1,m−1i=1;i−2,m+i−22≤i≤n2;i−2,n+m−i−2i=n2+1;n−i+2,n+m−i−2n2+2≤i≤n−1;2,m−1i=n.
Forn odd,(26)rai|A=1,m−1i=1;i−2,m+i−22≤i≤n2;i−2,n+m−i−2n2+1≤i≤n2+2;n−i+2,n+m−i−2n2+3≤i≤n−1;2,m−1i=n.
All vertices have different representations, which imply thatdimLLTn,m≤2. So, we obtained dimLLTn,m=2.Theorem 14.
LetLLTn,m be line graph of line graph of dragon graph for n≥5 and m≥3. Then, edimLLTn,m=4.Proof.
SinceedimLLTn,m≥2, it is not a path graph Pn. All edges are labeled as ei=aiai+1:1≤i≤n and ej′=bjbj+1:0≤j≤m−2.(27)e1″=an−1b0,e2″=anb0,e3″=anb1,e4″=a1b1,e5″=b0b2.
A=a2,b0,b1,bm−1 is an edge resolving set of LLTn,m, and the representations of all edges with respect to A are as follows:(28)rej′|A=2,0,0,m−2,j=0;2,1,0,m−3,j=1;j+1,j−1,j−1,m−j−2,2≤j≤m−2,re1″|A=3,0,1,m−2,re2″|A=2,0,1,m−2,re3″|A=2,1,0,m−2,re4″|A=1,1,0,m−2,re5″|A=3,0,1,m−3.
Forn even,(29)rei|A=0,2,1,m−1i=1;i−2,i+1,i,m+i−22≤i≤n2−1;i−2,n−i−1,n−i,n+m−i−3n2≤i≤n2+1;n−i+1,n−i−1,n−i,n+m−i−3n2+2≤i≤n−2;2,1,1,m−1i=n−1;1,1,1,m−1i=n.
Forn odd,(30)rei|A=0,2,1,m−1i=1;i−2,i+1,i,m+i−22≤i≤n2−1;i−2,n−i−1,n−i−1,n+m−i−3i=n2;i−2,n−i−1,n−i,n+m−i−3i=n2+1;n−i+1,n−i−1,n−i,n+m−i−3n2+2≤i≤n−2;2,1,1,m−1i=n−1;1,1,1,m−1i=n.
All edges have different representations, which implies thatedimLLTn,m≤4. On the other hand, we have to show that edimLLTn,m≥4.
Suppose to the contrary thatedimLLTn,m=3, then we have the following possibilities. If the set A=ai,aj,ak where i,j,k=1,2,…,n and i≠j≠k is an edge resolving set for graph LLTn,m, then some edges have same representations as shown in Table 3 and in Table 4.
If the setA=bs,bt,bu where s,t,u=2,3,…,m and s≠t≠u is an edge resolving set for graph LLTn,m, then some edges have same representations as shown in Table 5.
If the setA=an,b0,b1 is an edge resolving set for graph LLTn,m, then some edges have same representations as shown in Tables 6 and 7.
The setA=an,b0,b1 is not an edge resolving set for graph LLTn,m because it did not resolve the following edges:(31)re1″|A=re5″|A,re1′|A=re4″|A,ren−1|A=ren−2|A.
Any combination of three vertices will not resolve the all edges of the graphLLTn,m. Hence, there is no edge resolving set with three vertices for LLTn,m which implies that edimLLTn,m≥4. So, we obtained edimLLTn,m=4.Table 3
Edge distance codes ofLLTn,m w.r.t. A=ai,aj,ak.
d.,.aiajak1≤i≤⌊n/2⌋1≤j≤⌊n/2⌋1≤k≤⌊n/2⌋e0′ijke2″ijke3″ijke4″i−1j−1k−1eni−1j−1k−1Table 4
Edge distance codes ofLLTn,m w.r.t. A=ai,aj,ak
d.,.aiajak⌊n/2⌋<i≤n−1⌊n/2⌋<j≤n−1⌊n/2⌋<k≤n−1e0′n−in−jn−ke2″n−in−jn−ke3″n−in−jn−ke1″n−i−1n−j−1n−k−1en−1n−i−1n−j−1n−k−1(32)re0′|A=re2″|A=re3″|A,re4″|A=ren|A,re1″|A=ren−1|A.Table 5
Edge distance codes ofLLTn,m w.r.t. A=bs,bt,bu.
d.,.bsbtbu2≤s≤m−12≤t≤m−12≤u≤m−1e5″s−2t−2u−2e′11s−2t−2u−2e1″s−1t−1u−1e2″s−1t−1u−1e3″s−1t−1u−1e4″s−1t−1u−1e0′s−1t−1u−1e1stuenstuen−1stuen−2stuTable 6
Edge distance codes ofLLTn,m w.r.t. A=an,b0,b1.
d.,.e1″e5″e′11A=an,b0,b11,0,11,0,11,1,0d.,.e4″enen−1A=an,b0,b11,1,00,1,10,1,1Table 7
Comparison of the metric dimension, edge metric dimension, and mixed metric dimension.
Tn,mLTn,mLSTn,mLLTn,mVertex metric dimensiondimΓ2222Edge metric dimensionedimΓ2224Mixed metric dimensionmdimΓ3335Theorem 15.
LetLLTn,m be line graph of line graph of dragon graph for n≥5 and m≥3. Then, mdimLLTn,m=5.Proof.
SinceedimLLTn,m≥3, it is not a path graph Pn. All edges are labeled as ei=aiai+1:1≤i≤n and ej′=bjbj+1:0≤j≤m−2.(33)e1″=an−1b0,e2″=anb0,e3″=anb1,e4″=a1b1,e5″=b0b2.
IfA=a2,a⌈n/2⌉+1,b0,b1,bm−1 is mixed resolving set of LLTn,m, then the representation of all edges with respect to A is as follows:(34)rej′|A=2,n2−1,0,0,m−2,j=0;2,n2,1,0,m−3,j=1;j+1,n2+i−2,j−1,j−1,m−j−2,2≤j≤m−2.re1″|A=3,n2−2,0,1,m−2,re2″|A=2,n2−1,0,1,m−2,re3″|A=2,n2−1,1,0,m−2,re4″|A=1,n2,1,0,m−2,re5″|A=3,n2−1,0,1,m−3.
Forn even,(35)rei|A=0,n2−i,2,1,m−1i=1;i−2,n2−i,i+1,i,m+i−22≤i≤n2−1;i−2,n2−i,n−i−1,n−i,n+m−i−3i=n2;i−2,i−n2−1,n−i−1,n−i,n+m−i−3i=n2+1;n−i+1,i−n2−1,n−i−1,n−i,n+m−i−3n2+2≤i≤n−2;2,i−n2−1,1,1,m−1i=n−1;1,i−n2−1,1,1,m−1i=n.
Forn odd,(36)rei|A=0,n2−i,2,1,m−1i=1;i−2,n2−i,i+1,i,m+i−22≤i≤n2−1;i−2,n2−i,n−i−1,n−i−1,n+m−i−3i=n2;i−2,n2−i,n−i−1,n−i,n+m−i−3i=n2+1;n−i+1,i−n2−1,n−i−1,n−i,n+m−i−3n2+2≤i≤n−2;2,i−n2−1,1,1,m−1,i=n−1;1,i−n2−1,1,1,m−1,i=n.
The representation of all vertices with respect toA is as follows:(37)rai|A=1,n2,2,1,m−1i=1;i−2,n2−i+1,i+1,i,m+i−22≤i≤n2−1;i−2,n2−i+1,n−i,i,n+m−i−2i=n2;i−2,n2−i+1,n−i,n−i+1,n+m−i−2i=n2+1;n−i+2,i−n2−1,n−i,n−i+1,n+m−i−2n2+2≤i≤n−1;2,n2−1,1,1,m−1,i=n.rbj|A=3,n2−1,0,1,m−2,j=0;2,n2,1,0,m−2,j=1;j+1,n2+j−2,j−1,j−1,m−j−1,2≤j≤m−2.
All vertices and edges have distinguished representations with respect to setA=a2,a⌈n/2⌉+1,b0,b1,bm−1, which implies that mdimLLTn,m≤5. On the other hand, we have to show that mdimLLTn,m≥5.
As we know that the edge metric dimension of line graph of line graph of dragon graph is 4,edimLLTn,m=4 by Theorem [6]. Let mdimLLTn,m=4 and set A1=a2,b0,b1,bm−1 be mixed resolving set. The set A1 did not resolve all edges and vertices as rei|A1=rai|A1 for 2≤i≤n/2−1 and rei|A1=rai+1|A1 for n/2+2≤i≤n−1. That is why we have to include one more vertex a⌈n/2⌉+1 in mixed resolving set which implies that mdimLLTn,m≥5.
If the setA2=a2,a⌈n/2⌉+1,b0,b1 is mixed resolving set, then it resolves all edges and vertices of LLTn,m. However, rej′|A2=rbj|A2 for 2≤j≤m−2. The set A2 did not resolve all edges and vertices of LLTn,m; this implies that mdimLLTn,m≥5.
If the setA3=a2,a⌈n/2⌉+1,b1,bm−1 is mixed resolving set of LLTn,m, then re3″|A3=re0′|A3; the set A3 did not resolve all edges of LLTn,m; this implies that mdimLLTn,m≥5.
If the setA4=a2,a⌈n/2⌉+1,b0,bm−1 is mixed resolving set of LLTn,m, then re2″|A4=re0′|A4; the set A4 did not resolve all edges of LLTn,m; this implies that mdimLLTn,m≥5.
If the setA5=a⌈n/2⌉+1,b0,b1,bm−1 is mixed resolving set of LLTn,m, then ran|A5=ren|A5, rb0|A5=re2″|A5, and rb1|A5=re4″|A5,; the set A5 did not resolve all edges and vertices of LLTn,m; this implies that mdimLLTn,m≥5.
It is clear thatmdimLLTn,m≥5 is also computed that no set of cardinality smaller than five is a mixed resolving set of LLTn,m. So, we obtained mdimLLTn,m=5.


## 6. Comparison of Vertex, Edge, and Mixed Metric Dimension of Dragon Graph

On the basis of some facts given in [17], one can easily conclude that these parameters are not comparable because there are some families graph Γ for which dimΓ<edimΓ, dimΓ=edimΓ, or dimΓ>edimΓ. Moreover, from [23], infinite families of graphs for which dimΓ>edimΓ is satisfied were described, which was an open problem presented in [17], where only one family satisfying this inequality was given. Any mixed metric generator is, by definition, also a metric generator and an edge metric generator. In this sense, the connection mdimΓ≥maxdimΓ,edimΓ [20] follows instantly. It is obvious that the vertex set of any graph Γ forms a mixed metric generator for any graph Γ. In addition, any vertex of Γ, as well as each incident edge with it, has the same distance to the vertex itself. In this respect, a single vertex in Γ cannot constitute a mixed metric generator.


## 7. Conclusion

In this article, we calculate the exact value of vertex, edge, and mixed dimension for dragon graph,Tn,m, line graph of dragon graph, LTn,m, paraline graph of dragon graph, LSTn,m, and line graph of line graph of dragon graph, LLTn,m. The vertex metric dimension for Tn,m, LTn,m, LSTn,m, and LLTn,m is constant and same; dimTn,m=dimLTn,m=dimLSTn,m=dimLLTn,m=2. The edge metric dimension for Tn,m, LTn,m, LSTn,m, and LLTn,m is constant but edimTn,m=edimLTn,m=edimLSTn,m=2<edimLLTn,m=4. The mixed metric dimension for Tn,m, LTn,m, LSTn,m, and LLTn,m is constant but mdimTn,m=mdimLTn,m=mdimLSTn,m=3<mdimLLTn,m=5. It is already known from [17] that there are graphs G for which dimΓ<edimΓ, dimΓ=edimΓ, or dimΓ>edimΓ. Moreover, dragon graph, Tn,m, line graph of dragon graph, LTn,m, and paraline graph of dragon graph, LSTn,m, are families of graphs for which dimΓ=edimΓ but line graph of line graph of dragon graph is LLTn,mdimΓ<edimΓ.



---

*Source: 1927181-2021-12-15.xml*