# Computation of the Fault-Tolerant Metric Dimension of Certain Networks

Authors: Humera Bashir; Zohaib Zahid; Michael Onyango Ojiema
Journal: Mathematical Problems in Engineering
 (2022)

---

## Body

## 1. Introduction and Preliminaries

The notion of metric dimension originated in the twentieth century by the work done by Slater [1, 2] and latter independently by Harary and Melter [2]. The initial concept was introduced to locate the intruder in any network but the development and impact of the notion was far reaching in coming years. Several applications of metric related network parameters can be seen in social networking, navigation, communications, and engineering, pharmaceutical chemistry. The fault tolerance of a networking system is its ability to perform in case of malfunction of one of the source nodes. The fault tolerant metric dimension of a network can be regarded as a process of uniquely identification of each node of a network in case a malfunction occurs in one of the source node. This allows fault tolerant metric dimension more adaptability and flexibility for practical purposes than the parent notion.For a simple networkN=VN,EN, the size of least distant route between any two of its nodes s,w is referred as distance between them, notated as ds,w. If ℜ=n1,n2,…,nt is an arrayed collection of nodes in N then the vector dn,nii=1t is called a representative vector of the node n wrt. ℜ notated as rn|ℜ. The collection ℜ containing distinct representative vectors corresponding to distinct nodes is referred as resolving collection of nodes. A resolving collection of nodes with least members is called basis for the network N and its size is referred as metric dimension of N, represented by dimN.The limitations in the parent notion of metric dimension of having deviation at only one position between the representative tuples of vertices led Estrado-Moreno et al., to introduce a generalized notion ofk− metric dimension in 2014 (see [3]). Thus, the notion of the k− metric dimension was introduced, which becomes the metric dimension, for k=1, denoted by dimN. The equivalent condition on the existence of k− metric basis and related results were presented by Estrado-Moreno et al. in [4]. Further the notion was explored in context of generalized metric spaces in [6] and respectively for lexicographic product of graphs and corona product of graphs, in [5, 6]. The extension of this concept to the more general case of non-necessarily connected graphs is studied in [7]. The complexity of some k− metric dimension problems revealed that its computation is NP-hard (see [8]). This motivated the study of notion k− metric dimension problems for particular values of k. The notion for k=2, is referred as fault tolerant metric dimension, which was introduced by Hernando in 2008 (see [9]). Here, we include a formal definition of the notion: Let ℜ=n1,n2,…,nl be an arrayed collection of nodes in N. If for each pair of nodes a,b∈VN their absolute difference representation ADa,b|ℜ=dNa,n1−dNb,n1,…,dNa,nl−dNb,nl contains more than one zeros, then the collection ℜ is referred as a fault-tolerant resolving set (FTRS) for N. An FTRS of the least size in N is called as fault tolerant metric basis (FTMB) and its size is the fault tolerant metric dimension (FTMD) of N, notated by ℘N.The notion FTMD have been extensively discussed by several researchers. In this regard, FTMD for prism related graphs and circulant graphs have been studies in [10, 11], FTMR of lexicographic product and some other classes have been discussed in [12, 13], FTMD of certain wheel related graphs can be seen in [14]. Further, FTMD for convex polytopes and triangular lattices are computed in [15, 16]. Recently, in 2020, Huo et al. computed FTMD for generalized prism graph and Mobious ladders and latter in 2021 Bashir et al. discussed FTMD of some classes of rotationally symmetric graphs (see [17, 18]). Some other related developments can also be seen in [19, 20]. Following are the two theorems which will be helpful in computing our main results.Theorem 1 (see [3]).
For any graphGdimG<℘G.Theorem 2 (see [3]).
IfG≠Pn, then℘G≥3.The symmetric planer graphs, like generalized Petersen and sunlet networks have key importance in the fields of telecommunication, navigation and networking due to the structure of these networks which results in uniform rate of data transfer and thereby optimizing the resources used.


### 1.1. Main Results

The study conducted in this article, lead to following main resultsTheorem 3.
(1)
Forn≥3,(1)℘Sn=3,ifnis3,5,7or9,4,else.(2)
Forn≥3,(2)℘Pn,1=3,ifn=3,4,else.(3)
Forn≥5,(3)℘Pn,2=4,for evenn,4or5,for oddn.The rest of the article is organized in the following manner: In Section2, the FTMD of family of n− sunlet graph Sn is computed. The Section 3 comprises of the computation of FTMD of family the generalized Petersen graph Pn,t, for t=1. We also computed the FTMD of Pn,2 for even n and some tight bounds are obtained for odd n. An application of the current work in context of navigational routing problem is furnished in Section 4. Lastly, the paper is concluded with open problems in Section 5.


## 1.1. Main Results

The study conducted in this article, lead to following main resultsTheorem 3.
(1)
Forn≥3,(1)℘Sn=3,ifnis3,5,7or9,4,else.(2)
Forn≥3,(2)℘Pn,1=3,ifn=3,4,else.(3)
Forn≥5,(3)℘Pn,2=4,for evenn,4or5,for oddn.The rest of the article is organized in the following manner: In Section2, the FTMD of family of n− sunlet graph Sn is computed. The Section 3 comprises of the computation of FTMD of family the generalized Petersen graph Pn,t, for t=1. We also computed the FTMD of Pn,2 for even n and some tight bounds are obtained for odd n. An application of the current work in context of navigational routing problem is furnished in Section 4. Lastly, the paper is concluded with open problems in Section 5.


## 2. The FTMD of family of then− sunlet graph

The family ofn− sunlet graph denoted by Sn is the graph obtained by attaching n pendant edges to a cycle graph Cn as shown in Figure 1. The vertex set VSn=ui,vi|1≤i≤n and edge set ESn=uiui+1,uivi|1≤i≤n, where subscripts are to be read modulo n. In the following lemma, the metric dimension of the family of n− sunlet graph Sn is presented.Figure 1
n− sunlet graph Sn.Lemma 1.
The metric dimension ofSn, for n≥3 is(4)dimSn=2,ifnis odd orn=4,3,else.Proof.
In order to prove the theorem, following cases can be considered:Case 1.
(Whenn is odd)
Letn=2m+1, for m≥1 and take ℜ=u1,un+1/2. Representation of the vertices ui and vi with respect to ℜ is shown in Table 1.
We can see that for alla,b∈VSn, ra|ℜ≠rb|ℜ. Hence, ℜ is a resolving set. This implies that dimSn≤2. Since, dimG=1 if and only if G is a path graph, therefore, dimSn=2.Table 1
Representation of nodes inSn for even n.
irui|ℜirvi|ℜ2≤i≤mi−1,m−i+11≤i≤m+1i,m−i+2m+2≤i≤nn−i+1,i−m−1m+2≤i≤nn−i+2,i−mCase 2.
(Whenn=4)
It can be easily verified thatℜ=v1,v2 is a minimal resolving set for Sn. Therefore, we have dimSn=2.Case 3.
(Whenn is even and n≥6)
Letn=2m, for m≥3 and take ℜ=u1,u2,un+2/2. Representation of the vertices ui and vi with respect to ℜ is shown in Table 2.
We can see that for alla,b∈VSn, ra|ℜ≠rb|ℜ. Hence, ℜ is a resolving set. Therefore, dimSn≤3. It is exclusively required to prove that dimSn≠2, for n≥6. This can be achieved by showing that Sn is unable to have a resolving set of order 2, leading to the following possibilities:a)
Ifℜ=u1,ui with 1<i≤m, then run|ℜ=rv1|ℜ.b)
Ifℜ=v1,vi, then run−1|ℜ=rvn|ℜ,if1<i<m,rv2|ℜ,ifi=m..c)
Ifℜ=u1,vi, then run−1|ℜ=rvn|ℜ,if1≤i<m,rv2|ℜ,ifi=m..d)
Ifℜ=v1,ui, then run−1|ℜ=rvn|ℜ,if1≤i<m,rv2|ℜ,ifi=m..
Hence, in all above possibilities, it is concluded thatSn does not have a 2 cardinality resolving set. This concludes the proof. □
The above lemma will be helpful in the following result.Table 2
Representation of nodes inSn for even n≥6.
irui|ℜirvi|ℜ3≤i≤mi−1,i−2,m−i+11≤i≤m+1i,i−1,m−i+2m+2≤i≤nn−i+1,n−i+2,i−m−1m+2≤i≤nn−i+2,n−i+3,i−mTheorem 4.
The FTMD of Sn, for n≥3 is(5)℘Sn=3,ifnis3,5,7or9,4,else.Proof.
In order to show the assertion, following cases can be considered:Case 1.
Whenn=3,5,7or9
It can be immediately confirmed thatℜ=v1,v2,v3, when n=3 and ℜ=v1,vn−1/2,vn−2, when n=5,7,9, are FTRSs for Sn. This implies that ℘Sn≤3. Since, by Lemma 1, Sn has metric dimension 2 (when n is odd), therefore, by using Theorem 1, it is clear that ℘Sn≥3. This implies that ℘Sn=3.Case 2.
(Whenn=4)
Takeℜ=u1,u2,u3,u4. Then the representation of the vertices ui and vi with reference to the above said set ℜ are rui|ℜ=0,1,2,1,ifi=1,1,0,1,2,ifi=2,2,1,0,1,ifi=3,1,2,1,0,ifi=4,. and rvi|ℜ=1,2,3,2,ifi=1,2,1,2,3,ifi=2,3,2,1,2,ifi=3,2,3,2,1,ifi=4..
We can observe that more than one zeros exist in theADa,b|ℜ, for each a,b∈VS4. Hence, ℜ is a FTRS. Therefore, in view of Lemma 1 togather with Theorem 1, we conclude that dimS4=2<℘S4≤4. The only thing that remains to show is ℘S4≠3. The Table 3 shows that S4 has no FTRS of cardinality 3. Hence, ℘S4=4.Table 3
3− subsets of VS4 and pair of vertices where absolute difference representation has atleast two zeros.
ℜx,yADx,y|ℜu1,u2,ui with 2<i≤4u4,v10,0,2u1,u3,u4u2,u40,2,0v1,v2,v3u2,u42,0,0v1,v2,v4u1,u30,0,2v1,v3,v4u2,u40,0,2u1,v1,vi with 1<i≤4u2,u40,0,2u1,v2,vi with 2<i≤4u4,v10,0,2u1,v3,v4u2,u40,0,2v1,u1,ui with 1<i≤4u2,u40,0,2v1,u2,u3u1,v22,0,0v1,u2,u4u1,u32,0,0v1,u3,u4u2,v32,0,0Case 3.
(Whenn is even and n≥6)
Letn=2m, for m≥3 and take ℜ=u1,u2,um+1,um+2. Representation of the vertices ui and vi with respect to ℜ is shown in Table 4.
We can observe that more than one zeros exist in theADa,b|ℜ, for each a,b∈VSn. Hence, ℜ is a FTRS. Now, by Lemma 1 and Theorem 1, we have ℘Sn=4.Table 4
Representation of nodes inSn for even n≥6.
irui|ℜirvi|ℜi=10,1,m,m−111,2,m+1,m2≤i≤mi−1,i−2,m+1−i,m+2−i2≤i≤m+1i,i−1,m+2−i,m+3−ii=m+1m,m−1,0,1i=m+2m,m+1,2,1m+2≤i≤nn−i+1,n−i+2,i−m−1,i−m−2m+3≤i≤nn−i+2,n−i+3,i−m,i−m−1Case 4.
(Whenn is odd and n≥11)
Letn=2m+1 with m≥5 and take ℜ=u1,u2,um+1,um+2. Representation of the vertices ui and vi with respect to ℜ is shown in Table 5.
Therefore, in lights of Lemma1 combined with the Theorem 1, we have dimSn=2<℘Sn≤4. The only thing that remains to show is ℘Sn≠3. In order to achieved that Sn is unable to have a FTRS of order 3, we have the following possibilities:a)
Ifℜ=u1,ui,uj such that i,j∈2,3,…,m+1 and i<j, then ADu1,v2|ℜ=2,0,0.b)
Ifℜ=u1,ui,uj such that i,j∈2,3,…,n and i≤m<j, then(6)ADun,v1|ℜ=0,0,1,ifj=m+1,0,0,2,else.
For pendant verticesvi, consider ℜ=v1,vi,vj with 1<i<j≤m+1 and 1≤i≤m<j≤n. The proofs are similar as Cases a and b respectively.c)
Ifℜ=u1,vi,vj, such that i,j∈1,2,…,m+1 and i<j, then ADun−1,vn|ℜ=0,0,2 for i=1, j=m+1 and(7)ADun,v1|ℜ=0,2,0,ifi=1,j≠m+1,0,0,1,ifi≠1,j=m+1,0,0,0,else.d)
Ifℜ=u1,vi,vj, such that i,j∈2,3,…,n and i≤m<j, then(8)ADun,v1|ℜ=0,0,1,ifj=m+1,0,0,2,else,
and ifℜ=u1,v1,vj, with m<j≤n, then ADun−1,vn|ℜ=0,0,2.e)
Ifℜ=v1,ui,uj, such that i,j∈1,2,…,m+1 and i<j, then(9)ADvn,un−1|ℜ=0,0,0,if1≤i<j≤m−1,0,0,2,if1≤i≤m−1,m≤j≤m+1,
andADvm+1,um+2|ℜ=1,0,0 for i=m,j=m+1.f)
Ifℜ=v1,ui,uj, such that i,j∈1,2,…,n and i≤m<j, then(10)ADun−1,vn|ℜ=0,0,1,forj=m,0,0,0,forj=n,0,0,2,otherwise.
Hence, in all above possibilities, we conclude that there is no FTRS forSn containing exactly 3 nodes. This concludes the proof. □Table 5
Representation of nodes inSn for odd n≥11.
irui|ℜirvi|ℜi=10,1,m,m11,2,m+1,m+12≤i≤m+1i−1,i−2,m+1−i,m+2−i2≤i≤m+1i,i−1,m+2−i,m+3−ii=m+2m,m,0,1i=m+2m+1,m+1,2,1m+3≤i≤nn−i+1,n−i+2,i−m−1,i−m−2m+3≤i≤nn−i+2,n−i+3,i−m,i−m−1


## 3. The FTMD of family of The Generalized Petersen graphsPn,t

Coxeter was the first one to introduce the generalized notion of Petersen graphsPn,t in 1950 (see [23]). It is an important class of graphs with vertex set VPn,t=ui,vi|1≤i≤n and edge set EPn,t=vivi+1,uivi,uiui+t|1≤i≤n, where subscripts are to be read modulo n and 1≤t≤n−1/2. The Petersen graphs P8,1 and P8,2 are shown in Figures 2 and 3 respectively.Figure 2
The Petersen graphP8,1.Figure 3
The Petersen graphP8,2.The forthcoming lemma will be resourceful in the computation the FTMD in regards to family of the generalized Petersen graphPn,1.Lemma 2 (see [24]).
For the generalized Petersen graphPn,1;(11)dimPn,1=2,for oddn,3,for evenn.Theorem 5.
The FTMD ofPn,1, forn≥3is(12)℘Pn,1=3,ifn=3,4,else.Proof.
In order to show the assertion, following cases can be considered:Case 1.
(Whenn is even)
Takeℜ=u1,u2,v1,v2, then for the vertices ui and vi the representation is shown in Table 6.
Since it can be observed that more than one zeros exist in theADa,b|ℜ, for each a,b∈VPn,1. Therefore, ℘Pn,1≤4. Hence, in view of Lemma 2 together with the Theorem 1, we conclude that ℘Pn,1=4.Table 6
Representation of nodes inPn,1 for even n.
irui|ℜrvi|ℜ10,1,1,21,2,0,12≤i≤m+1i−1,i−2,i,i−1i,i−1,i−1,i−2m+2≤i≤nn−i+1,n−i+2,n−i+2,n−i+3n−i+2,n−i+3,n−i+1,n−i+2Case 2.
(Whenn is odd)
This case is further subdivided as follows:Case 2a.
(Whenn=3)
ForP3,1 is can be confirmed immediately that ℜ=u1,u2,u3 is its FTRS. This implies that ℘P3,1≤3. Therefore, in view of the Lemma 2 and the Theorem 1, we conclude that ℘P3,1=3.Case 2b.
(Whenn is odd and n≥5)
Letn=2m+1, for m≥1 and take ℜ=u1,u2,v1,v2, then for the vertices ui and vi the representation is shown in Table 7.
Since it can be observed that more than one zeros exist in theADa,b|ℜ, for each a,b∈VPn,1. Therefore, ℘Pn,1≤4. Hence, in view of Lemma 3 and Theorem 1, we have dimPn,1=2<℘Pn,1≤4. It is exclusively required to prove that ℘Pn,1≠3. This can be achieved by showing that Pn,1 is unable to have a resolving set of order 3, leading to the following possibilities:a)
Ifℜ=u1,ui,uj such that i,j∈2,3,…,m+1 and i<j, then ADu1,v2|ℜ=2,0,0.b)
Ifℜ=u1,ui,uj such that i,j∈2,3,…,n and i≤m<j, then(13)ADun,v1|ℜ=0,0,1,ifj=m+1,0,0,2,else.c)
Ifℜ=u1,vi,vj, such that i,j∈1,2,…,m and i<j, then ADu1,vn|ℜ=2,0,0 and if j=m+1, then(14)ADv1,u2|ℜ=0,2,0,ifi=1,0,0,0,2≤i≤m.d)
Ifℜ=u1,vi,vj, such that i,j∈1,2,…,n and i≤m<j, then(15)ADv1,u2|ℜ=0,0,0,ifi≠1,j=m+1,0,0,2,ifi≠1,j≠m+1,0,2,0,ifi=1,j=m+1,
and ifi=1 and j≠m+1 then ADun,v1|ℜ=0,2,0.
Therefore, all the aforesaid cases reveal thatPn,1 have not FTRS of cardinality 3. This concludes the proof. □
The upcoming theorem will be aided by the following lemma.Table 7
Representation of nodes inPn,1 for odd n≥5.
irui|ℜrvi|ℜ10,1,1,21,2,0,12≤i≤m+1i−1,i−2,i,i−1i,i−1,i−1,i−2i=m+2m,m,m+1,m+1m+1,m+1,m,mm+3≤i≤nn−i+1,n−i+2,n−i+2,n−i+3n−i+2,n−i+3,n−i+1,n−i+2Lemma 3 (see [21]).
Forn≥5,dimPn,2=3.Theorem 6.
The FTMD ofPn,2, forn≥5is(16)℘Pn,2=4,for evenn,4or5,for oddn.Proof.
In order to prove the theorem, following cases can be considered:Case 1.
(Whenn is even)
The case is further subdivied as follows:Case 1a.
(Whenn=6)
It can be immediately confirmed thatℜ=u1,u3,u5,v1 is a FTRS for P6,2. This implies that ℘P6,2≤4. Therefore, in lights of Lemma 3.3 combined with Theorem 1, it is concluded that ℘P6,2=4.Case 1b.
(Whenn≡0mod4 and n≥8)
Letn=2m, for even m≥4 and take ℜ=u1,u3,um+1,um+3. Then for the vertices ui and vi the representations are shown in Table 8 and 9.Table 8
Representation of nodes inPn,2 for n≡0mod4n≥8 and even i.
i (even)rui|ℜrvi|ℜi=23,3,m+4/2,m+4/22,2,m+2/2,m+2/24≤i≤mi+4/2,i+2/2,m−i+6/2,m−i+8/2i+2/2,i/2,m−i+4/2,m−i+6/2i=m+2m+4/2,m+4/2,3,3m+2/2,m+2/2,2,2m+4≤i≤nn−i+6/2,n−i+8/2,i−m+4/2,i−m+2/2n−i+4/2,n−i+6/2,i−m+2/2,i−m/2Table 9
Representation of nodes inPn,2 for n≡0mod4n≥8 and odd i.
i (odd)rui|ℜrvi|ℜ10,1,m/2,m−2/21,2,m+2/2,m/23≤i≤m−1i−1/2,i−3/2,m−i+1/2,m−i+3/2i+1/2,i−1/2,m−i+3/2,m−i+5/2i=m+1m/2,m−2/2,0,1m+2/2,m/2,1,2m+3≤i≤n−1n−i+1/2,n−i+3/2,i−m−1/2,i−m−3/2n−i+3/2,n−i+5/2,i−m+1/2,i−m−1/2Case 1c.
(Whenn≡2mod4 and n≥10)
Letn=2m, for odd m≥5 and take ℜ=u1,u3,um+2,um+4. Then for the vertices ui and vi the representations are shown in Table 10 and 11.
The Cases 1b and 1c indicates that more than one zeros exist in theADa,b|ℜ, for each a,b∈VPn,2 implying that ℘Pn,2≤4. Therefore, in lights of Lemma 3 combined with the Theorem 1, we conclude that ℘Pn,2=4.Table 10
Representation of nodes inPn,2 for n≡2mod4 and n≥10 and even i.
i (even)rui|ℜrvi|ℜi=23,3,m+5/2,m+3/22,2,m+3/2,m+1/24≤i≤m+1i+4/2,i+2/2,m−i+7/2,m−i+9/2i+2/2,i/2,m−i+5/2,m−i+7/2i=m+3m+3/2,m+5/2,3,3m+1/2,m+3/2,2,2m+5≤i≤nn−i+6/2,n−i+8/2,i−m+3/2,i−m+1/2n−i+4/2,n−i+6/2,i−m+1/2,i−m−1/2Table 11
Representation of nodes inPn,2 for n≡2mod4 and n≥10 and odd i.
i (odd)rui|ℜrvi|ℜ10,1,m−1/2,m−3/21,2,m+1/2,m−1/2i=31,0,m−1/2,m−1/22,1,m+1/2,m+1/25≤i≤mi−1/2,i−3/2,m−i+2/2,m−i+4/2i+1/2,i−1/2,m−i+4/2,m−i+6/2i=m+2m−1/2,m−1/2,0,1m+1/2,m+1/2,1,2i=m+4m−3/2,m−1/2,1,0n−i+3/2,n−i+5/2,i−m/2,i−m−2/2m+6≤i≤nn−i+1/2,n−i+3/2,i−m−2/2,i−m−4/2n−i+3/2,n−i+5/2,i−m/2,i−m−2/2Case 2.
(Whenn≃1 mod 2)
The case is further divided as below:Case 2a.
(Whenn=5,7)
It can be immediately confirmed thatℜ=u1,u2,v3,v5 and ℜ=u1,u2,v6,v7 is FTRS for P5,2 and P7,2 respectively. This implies that ℘Pn,2≤4 for n=5,7. Therefore, in lights of Lemma 3 combined with Theorem 1, it is concluded that ℘Pn,2=4 for n=5,7.Case 2b.
(Whenn≡1mod4 and n≥9)
Letn=2m+1, for even m≥4 and take ℜ=un−1,un,vm+2,vm+3,vn, then for the vertices ui and vi the representations are shown in Table 12 and 13.Table 12
Representation of nodes inPn,2 for n≡1mod4 and n≥9 and even i.
i (even)rui|ℜrvi|ℜi=24,1,m+2/2,m+2/2,23,2,m+4/2,m+4/2,24≤i≤m−4i+6/2,i/2,m−i+4/2,m−i+6/2,i+2/2i+4/2,i+2/2,n−i−5/2,n−i−3/2,i+4/2i=m−2m+2/2,m−2/2,3,4,m/2i+4/2,i+2/2,n−i−5/2,n−i−3/2,i+4/2i=mn−m−1/2,m/2,2,3,m+2/2m+2/2,m+2/2,2,3,m+4/2i=m+2n−m−3/2,m+2/2,1,2,m+2/2m/2,m+2/2,0,1,m+4/2i=m+4n−i−1/2,n−i+5/2,i−m/2,i−m/2,n−i+3/2n−m−3/2,n−m−1/2,2,1,n−m+1/2i=m+6n−i−1/2,n−i+5/2,i−m/2,i−m/2,n−i+3/2n−m−5/2,n−m−3/2,4,3,n−m−6m+8≤i≤n−3n−i−1/2,n−i+5/2,i−m/2,i−m/2,n−i+3/2n−i+1/2,n−i+3/2,i−m+2/2,i−m+2/2,n−i+3/2i=n−10,3,m/2,m+2/2,21,2,m+2/2,m+2/2,1Table 13
Representation of nodes inPn,2 for n≡1mod4 and n≥9 and odd i.
i (odd)rui|ℜrvi|ℜi=11,3,m+2/2,m+2/2,22,2,m+4/2,m+4/2,13≤i≤m−3i+1/2,i+5/2,n−i−6/2,n−i−6/2,i+3/2i+3/2,i+3/2,n−i−4/2,n−i−4/2,i+5/2i=m−1m/2,m+2/2,n−m−7/2,n−m−7/2,m+2/2i+3/2,i+3/2,n−i−4/2,n−i−4/2,i+5/2i=m+1m+2/2,m/2,2,2,m+2/2m+2/2,m+2/2,1,2,n−m+3/2i=m+3n−i+4/2,n−i/2,i−m+1/2,i−m−1/2,n−i+2/2m+2/2,m/2,1,0,m+4/2i=m+5n−i+4/2,n−i/2,i−m+1/2,i−m−1/2,n−i+2/2n−m−3/2,n−m−3/2,3,2,n−m−1/2m+7≤i≤n−2n−i+4/2,n−i/2,i−m+1/2,i−m−1/2,n−i+2/2n−i+2/2,n−i+2/2,i−m+3/2,i−m+1/2,n−ii=n3,0,m+2/2,m/2,12,1,m+2/2,m+2/2,0Case 2c.
(Whenn≡3mod4 and n≥11)
Letn=2m+1, for odd m≥5 and take ℜ=un−1,un,vm+2,vm+3,vn−1,then the representations of the vertices ui and vi are shown in Table 14 and 15.
The Cases 2b and 2c indicates that more than one zeros exist in theADa,b|ℜ, for each a,b∈VPn,2. Hence, ℜ is a FTRS. Hence, in view of Lemma 3 combined with the Theorem 1, we conclude that dimPn,2=3<4≤℘Pn,2≤5. This concludes the proof. □Table 14
Representation of nodes inPn,2 for n≡3mod4 and n≥11 and even i.
i (even)rui|ℜrvi|ℜi=2i+6/2,i/2,n−i−7/2,n−i−7/2,i+4/23,2,m+5/2,m+5/2,34≤i≤m−3i+6/2,i/2,n−i−7/2,n−i−7/2,i+4/2i+4/2,i+2/2,n−i−5/2,n−i−5/2,i+6/2i=m−1m+1/2,m−1/2,3,3,m+3/2n−m+2/2,m+1/2,3,4,m+5/2i=m+1m−1/2,m+1/2,2,2,m+2/2n−m/2,m+3/2,1,2,m+3/2i=m+3n−i−1/2,n−i+5/2,i−m+1/2,i−m−1/2,n−i+1/2m−1/2,m+3/2,1,0,m−1/2i=m+5n−i−1/2,n−i+5/2,i−m+1/2,i−m−1/2,n−i+1/2m−3/2,m−1/2,3,2,m−1/2m+7≤i≤n−3n−i−1/2,n−i+5/2,i−m+1/2,i−m−1/2,n−i+1/2n−i+1/2,n−i+3/2,i−m+3/2,i−m+1/2,n−i−1i=n−10,3,m+1/2,m−1/2,11,2,m+1/2,m−1/2,0Table 15
Representation of nodes inPn,2 for n≡3mod4 and n≥11 and odd i.
i (odd)rui|ℜrvi|ℜi=11,3,m+3/2,m+1/2,22,2,m−3,m−4,23≤i≤m−2i+1/2,i+5/2,n−i−8/2,n−i−6/2,i+3/2i+3/2,i+3/2,n−i−6/2,n−i−4/2,i+5/2i=mi+1/2,n−i/2,n−i−8/2,n−i−6/2,n−i+2/2m+3/2,m+3/2,2,3,m+5/2i=m+2i+1/2,n−i/2,n−i−8/2,n−i−6/2,n−i+2/2m+1/2,m+1/2,0,1,m+1/2m+4≤i≤m+6n−i+3/2,n−i−1/2,i−m/2,i−m/2,n−i+2/2n−i+2/2,n−i+2/2,i−m−2,i−m−3,n−i+4/2m+8≤i≤n−2n−i+3/2,n−i−1/2,i−m/2,i−m/2,n−i+2/2n−i+2/2,n−i+2/2,i−m+2/2,i−m+2/2,n−i−1i=n3,0,m+1/2,m+3/2,22,1,i−m+2/2,i−m+2/2,1Remark 1.
This can be verified easily that℘Pn,2=4, when n=15, by using the resolving set ℜ=u1,u2,v5,v8. Similarly, it can be verified that ℘Pn,2≠4, for n=17.


## 4. Application

The current section is included with an application of FTMD in context of navigational optimization problem is discussed. The essence of a navigational routing problem is to reach targeted location and avoiding mixing of apparently similar locations. If the targeted locations are referred as nodes and the roads connecting them as edges of a network, then the process of uniquely identifying each node of the network with respect to certain minimum collection of its reference nodes is a realization of metric dimension in networks. Further, if one of the location in the reference collection of nodes is unreachable, then the minimum number of such reference nodes providing unique identification of each location in network is realization of FTMD of network. As an illustrative case, consider navigating in a networkP8,2, consisting of node set VP8,2=u1,u2,u3,u4,u5,u6,u7,u8,v1,v2,v3,v4,v5,v6,v7,v8 as shown in Figure 3. Then the unique identification of each node with respect to minimum collection of reference nodes ℜ=u1,u3,u5,u7 is shown in Table 16.Table 16
Representation of nodes inP8,2 with respect to ℜ.
irui|ℜrvi|ℜ10,1,2,11,2,3,223,3,4,42,2,3,331,0,1,22,1,2,344,3,3,43,2,2,350,1,0,13,2,1,264,4,3,33,3,2,271,2,1,02,3,2,183,4,4,32,3,3,2It can be seen that the setℜ is minimum set representing each node uniquely even if one of the nodes in it is unreachable. Therefore, it is concluded that if the navigation coordinates is in accordance with the set ℜ, then the navigational routing will be optimal.


## 5. Conclusion

In the current study, the FTMD of the familiesn− sunlet graph Sn and the generalized Petersen graph Pn,t, for t=1 is computed, which were found to be constant. We also computed the constant FTMD of Pn,2 for even n and tight bounds are obtained for odd n. Finally, the article is concluded with the following open problems. [22–25].Open Problem 1.
For what values of oddn the FTMD of family of the generalized Petersen graph Pn,2 is 4 or 5.Open Problem 2.
Find the FTMD of family of the generalized Petersen graphsPn,t for t≥3.



---

*Source: 6385673-2022-03-21.xml*