# Fault-Tolerant Resolvability in Some Classes of Subdivision Graphs

Authors: Muhammad Faheem; Zohaib Zahid; Dalal Alrowaili; Imran Siddique; Aiyared Iampan
Journal: Journal of Mathematics
 (2022)

---

## Abstract

The concept of resolving sets (RSs) and metric dimension (MD) invariants have a wide range of applications in robot navigation, computer networks, and chemical structure. RS has been used as a sensor in an indoor positioning system to find an interrupter. Many terminologies in machine learning have also been used to diagnose the interrupter in the systems of marine and gas turbines using sensory data. We proposed a fault-tolerant self-stable system that allows for the detection of an interrupter even if one of the sensors in the chain fails. If the elimination of any element from a RS is still a RS, then the RS is considered as a fault-tolerant resolving set (FTRS), and the fault-tolerant metric dimension (FTMD) is its minimum cardinality. In this paper, we calculated the FTMD of the subdivision graphs of the necklace and prism graphs. We also found that this invariant has constant values for both graphs.


---

## Body

## 1. Introduction and Preliminaries

LetG be a connected, undirected, finite, and simple graph with vertex set VG and edge set EG. The number of edges in the shortest x−y path between two vertices x,y∈VG is known as the distance dGx,y between them. The cardinality of edges that are incident to a vertex x is called degree dGx of x. Let W=w1,w2,…,ws be an ordered subset of VG and y∈VG; then, the s-tuple dGy,w1,dGy,w2,…,dGy,ws is the distance-vector representation of y with respect to W and is denoted by ry|W. If distance-vector representations ry|W are distinct for every vertex y of G, then W is known as the RS. The metric basis of G is the minimum number of elements in a RS, and the cardinality of the basis is called the MD of G, denoted by βG. For W=w1,w2,…,ws⊂VG, the ith component of ry|W is 0 if and only if y=wi. So, W would be a RS if rx|W≠ry|W for each pair x≠y∈VG\W. The absolute difference representation consists of s-vector dGx,w1−dGy,w1,…,dGx,ws−dGy,ws for any x,y∈VG with respect to W, and it is denoted by ADx,y|W. The absolute difference representation is another concept to define the RS. If ADx,y|W has at least one nonzero element in its s-vector for every x≠y∈VG, then W is called the RS. For more details, we refer to [1, 2].In 1975, when Slater was working with Coast Guard Loran and US Sonar (long range aids to navigation) station, he described the notion of RSs in graphs [3, 4]. Harary and Melter independently described this idea in 1976 [5]. The RSs were introduced to locate the interrupter in a computer network. After that, in 2003, Chartrand and Zhang used metric bases in the fields of biology, robotics, and chemistry [6, 7]. Many techniques have been used in machine learning to find the interrupter using sensory data. In 2021, Tan et al. compared the data-driven and model-driven methods for the diagnosis of interrupters in marine machinery systems [8].It will be a difficult task to locate an interrupter if one of the sensors does not work properly. To tackle such problems, Hernando et al. gave the idea of a FTRS [9]. If the elimination of any element from a RS is again a RS, then the RS is considered as a FTRS. Formally, for any RS W′ of G, if W′w is also a RS for any w∈W′, then W′ is called a FTRS of G. In other words, ADx,y|W′ contains at least two elements that are nonzero in the s-vector for all x≠y∈VG. The FTMD is the minimum cardinality of a FTRS, and it is denoted by β′G.Hernando et al. in [9] studied the concept of the FTMD and computed it for the tree graph. They also found an important upper bound for the FTMD of graph G, which is β′G≤βG1+2.5βG−1. Voronov in [10] determined the upper bound for the FTMD of the king’s graph. Hussain et al. in [11] proved that the FTMD is constant for the antiweb graph and unbounded for the gear and antiweb gear graphs.Raza et al. in [12] studied the bounds for the FTMD of some families of convex polytopes. In [13], Raza et al. proved some bounds for the FTMD of extended Petersen, antiprism, and squared cycle graphs. Raza et al. in [14] found some bounds for the FTMD by considering the graphs of m,n-dimension grid networks, hexagonal networks, and honeycomb networks. Zheng et al. in [15] calculated the precise values for the FTMD of the generalized wheels and some families of convex polytopes. Afzal and others in [16] gave some important results and proved that there exist some families of convex polytopes, which have unbounded MD and FTMD. Basak et al. in [17] calculated the FTMD for the circulant graph. Somasundari and Raj in [18] calculated the fault-tolerant resolvability for the interconnections of oxide networks.Javaid et al. in [19] computed the exact value of the FTMD of the cycle graph. Hayat et al. in [20] calculated some upper bounds for the FTMD for r-dimensional bens, r-dimensional butterfly, and silicate networks. Simic et al. in [21] contributed great work about the FTMD and computed the precise value for the grid graph. Laxman in [22] computed the lower bound of the FTMD for the cube of the path graph. Recently, the FTMD for the line graphs was studied by Guo et al. in [23], and they computed it for the line graphs of the prism and necklace graphs.The subdivision graphSG of any graph G can be obtained by adding a new vertex to each edge of the graph G as shown in Figures 1 and 2. In this paper, we computed the FTMD of the subdivision graphs of the necklace and the prism graphs. The results of the FTMD in subdivision graphs are known only for cycle and path graphs as shown in the following theorem.Figure 1
Subdivision of necklace graphSNe6.Figure 2
Subdivision of prism graphSYn.Theorem 1.
For anyn≥2 and n≥3, we have β′SPn=2 and β′SCn=3, respectively, where Pn is the path graph and Cn is the cycle graph.Since it is not an easy task to calculateβ′G for any graph G, Estrado-Moreno et al. computed some important bounds on β′G of every graph G as follows.Lemma 1 (see [24]).
LetG be any graph; then, we have βG<β′G.Lemma 2 (see [24]).
LetG≠Pn be any graph; then, we have β′G≥3.Khuller et al. [25] gave an essential result for every graph G with 2 of its MD as follows.Lemma 3 (see [25]).
LetβG=2, for any graph G, and let v1,v2⊂VG be a RS in G. Then, dGv1≤3 and dGv2≤3.Therefore, similar property works for every graphG with 3 of its β′G as presented in the following lemma.Lemma 4.
Letβ′G=3, for any graph G, and let v1,v2,v3⊂VG be a FTRS in G. Then, dGv1≤3, dGv2≤3, and dGv3≤3.We will discuss and compute the precise results ofβSNen as well as β′SNen, where Nen is a necklace graph in Section 2. We will calculate the exact value of β′SYn by considering Yn as a prism graph in Section 3.


## 2. The Fault-Tolerant Metric Dimension for the Subdivision of the Necklace Graph

The necklace graphNen for n≥3 consists of the vertices xi,yj:0≤i≤n+1,1≤j≤n as shown in Figure 3.Figure 3
Necklace graphNe6.Now, to computeβ′SNen, we need to convert the necklace graph into its subdivision graph. The subdivision graph of the necklace graph SNen is shown in Figure 1.The result about the MD for the subdivision graph of the necklace graph is presented in the following theorem.Theorem 2.
For any integern≥3, we have βSNen=3.Proof.
Following are the cases to compute the required results:Case 1.
(whenn is odd).
TakeW=x0,un+1/2,vn+3/2⊆VSNen for all odd integers n≥3. We need to prove that W is the RS for the graph SNen. To prove this, we give distance-vector representations of every vertex in SNen. Representation of the vertices xρ where 0≤ρ≤n+1 is(1)rxρ|W=0,n,2+n,ifρ=0,2ρ,−2ρ+n,4−2ρ+n,if1≤ρ≤n−12,1+n,1,3,ifρ=1+n2,2−ρ+2+n,2ρ−n2,2−n2−1+ρ,if3+n2≤ρ≤1+n.
Representation of the verticesuρ where 1≤ρ≤1+n is(2)ruρ|W=−1+2ρ,−2ρ+1+n,−2ρ+5+n,if1≤ρ≤1+n2,2+n,2,2,ifρ=3+n2,5+2−ρ+n,−n−1+2ρ,−n−3+2ρ,if5+n2≤ρ≤1+n.
Representation of the verticeswρ where 1≤ρ≤1+n is(3)rwρ|W=−1+2ρ,−2ρ+3+n,−2ρ+5+n,if1≤ρ≤n−12,n,4,4,ifρ=1+n2,2+n,4,2,ifρ=3+n2,5−2ρ+2n,−n+1+2ρ,−3−n+2ρ,if5+n2≤ρ≤1+n.
Representation of the verticesvρ where 1≤ρ≤1+n is(4)rvρ|W=1+2ρ,−2ρ+1+n,−2ρ+5+n,if1≤ρ≤n−12,2+n,2,4,ifρ=1+n2,2+n,4,0,ifρ=3+n2,−2ρ+5+2n,−n+1+2ρ,−n−1+2ρ,if5+n2≤ρ≤n,1,n+1,1+n,ifρ=1+n.
Representation of the verticesyρ where 1≤ρ≤n is(5)ryρ|W=2ρ,−2ρ+2+n,4−2ρ+n,if1≤ρ≤n−12,1+n,3,3,ifρ=1+n2,−2ρ+4+2n,−n+2+2ρ,−n−2+2ρ,if3+n2≤ρ≤n.
The distance-vector representations are distinct for all the vertices ofSNen. So, W is the RS. Hence, βSNen≤3. Now, in order to prove that βSNen≥3, suppose contrary that βSNen=2, and according to Lemma 3, we have the following possibilities:(1)
LetW=xi,xj⊂VSNen for 0≤i<j≤n+1/2; then, we have the following subcases:(i)
ADun+1,wn+1|W=0,0 for j≠n+1/2.(ii)
ADun+3/2,vn+1/2|W=0,0 for j=n+1/2.So,W is not the RS.(2)
LetW=ui,uj⊂VSNen for 0≤i<j≤n+1/2; then, we have the following subcases:(i)
ADun+1,wn+1|W=0,0 for j≠n+1/2.(ii)
ADun+3/2,vn+1/2|W=0,0 for j=n+1/2.So,W is not the RS.(3)
LetW=xi,xj⊂VSNen for 0≤i≤n+1/2 and n+3/2≤j≤n+1; then, we have the following subcases:(a) Whenn=3:(i)
ADv3,w3|W=0,0 for j≠3.(ii)
ADu3,v3|W=0,0 for i=0 and j=3.(iii)
ADu4,v3|W=0,0 for i=1,2 and j=3.(b) Whenn≥5:(i)
ADvn,wn|W=0,0 for j≠n.(ii)
ADun,vn|W=0,0 for 0≤i≤n−3/2 and j=n.(iii)
ADv1,w2|W=0,0 for n−1/2≤i≤n+1/2 and j=n.So,W is not the RS.(4)
LetW=ui,uj⊂VSNen for 1≤i≤n+1/2 and n+3/2≤j≤n+1; then, we have the following subcases:(a) Whenn=3:(i)
ADv1,v4|W=0,0 for i=1 and j=3.(ii)
ADu3,w4|W=0,0 for i=1 and j=4.(iii)
ADw2,w3|W=0,0 for i=2 and j=3.(iv)
ADu1,v2|W=0,0 for i=2 and j=4.(b) Whenn=5:(i)
ADv5,w5|W=0,0 for j≠5,6.(ii)
ADx3,y5|W=0,0 for i=1 and j=5.(iii)
ADv3,v6|W=0,0 for i=2 and j=5.(iv)
ADv1,w2|W=0,0 for i=3 and j=5.(v)
ADu5,v5|W=0,0 for i=1 and j=6.(vi)
ADv1,u3|W=0,0 for i=2 and j=6.(vii)
ADv1,w2|W=0,0 for i=3 and j=6.(c) Whenn≥7:(i)
ADvn,wn|W=0,0 for j≠n,n+1.(ii)
ADun−1,vn−1|W=0,0 for i=1,2 and j=n.(iii)
ADv1,w2|W=0,0 for 3≤i≤n+1/2 and j=n.(iv)
ADun,vn|W=0,0 for i=1,2 and j=n+1.(v)
ADv1,w2|W=0,0 for 3≤i≤n+1/2 and j=n+1.So,W is not the RS.(5)
LetW=xi,uj⊂VSNen for 0≤i≤n+1/2 and 1≤j≤n+1/2; then, ADvn,wn|W=0,0. So, W is not the RS.(6)
LetW=xi,vj⊂VSNen for 0≤i≤n+1/2 and 1≤j≤n+1/2; then, we have the following subcases:(i)
ADun+1,wn+1|W=0,0 for i≠n+1/2.(ii)
ADun+5/2,vn+3/2|W=0,0 for i=n+1/2.So,W is not the RS.(7)
LetW=ui,vj⊂VSNen for 1≤i≤n+1/2 and 1≤j≤n+1/2; then, we have the following subcases:(i)
ADun+1,wn+1|W=0,0 for i≠n+1/2.(ii)
ADun+5/2,vn+3/2|W=0,0 for i=n+1/2.So,W is not the RS.(8)
LetW=xi,yj⊂VSNen for 0≤i≤n+1/2 and 1≤j≤n+1/2; then, we have the following subcases:(i)
ADun+1,wn+1|W=0,0 for i≠n+1/2 and j≠n+1/2.(ii)
ADun+1/2,vn+1/3|W=0,0 for i=n+1/2 and j≠n+1/2.(iii)
ADun,vn|W=0,0 for i=0 and j=n+1/2.(iv)
ADvn+1/2,wn+1/2|W=0,0 for 1≤i≤n−1/2 and j=n+1/2.(v)
ADun+1/2,un+3/2|W=0,0 for i=n+1/2 and j=n+1/2.So,W is not the RS.(9)
LetW=ui,wj⊂VSNen for 1≤i≤n+1/2 and 1≤j≤n+1/2; then, we have the following subcases:(a) Whenn=3:(i)
ADu4,w4|W=0,0 for i=1 and j=1.(ii)
ADu1,v1|W=0,0 for i=2 and j=1.(iii)
ADv1,w1|W=0,0 for i=1 and j=2.(iv)
ADx1,x2|W=0,0 for i=2 and j=2.(10)
LetW=ui,yj⊂VSNen for 1≤i≤n+1/2 and 1≤j≤n+1/2; then, we have the following subcases:(i)
ADun+1,wn+1|W=0,0 for i≠n+1/2 and j≠n+1/2.(ii)
ADun−1/2,vn−1/2|W=0,0 for i=n+1/2 and j≠n−1/2,n+1/2.(iii)
ADun−1/2,vn+1/2|W=0,0 for i=n+1/2 and j=n−1/2.(iv)
ADvn+1/2,wn+1/2|W=0,0 for i≠n+1/2 and j=n+1/2.(v)
ADwn+1/2,wn+3/2|W=0,0 for i=n+1/2 and j=n+1/2.So,W is not the RS.
We deduce to contradict in all the possibilities. So, there is no RS with cardinality 2. This shows thatβSNen≥3. Hence, βSNen=3.Case 2.
(whenn is even).
TakeW=x0,un/2,yn/2⊆VSNen for all even integers n≥4. Representation of the vertices xρ where 0≤ρ≤1+n is(6)rxρ|W=0,−1+n,n,ifρ=0,2ρ,−2ρ−1+n,−2ρ+2+n,if1≤ρ≤n−22,n,1,2,ifρ=n2,4−2ρ+2n,−n+1+2ρ,2−n+2ρ,if2+n2≤ρ≤n,2,n+1,2+n,ifρ=1+n.
Representation of the verticesuρ where 1≤ρ≤1+n is(7)ruρ|W=−1+2ρ,−2ρ+n,3−2ρ+n,if1≤ρ≤n2,1+n,2,3,ifρ=2+n2,−2ρ+5+2n,−n+2ρ,−n+1+2ρ,if4+n2≤ρ≤1+n.
Representation of the verticeswρ where 1≤ρ≤1+n is(8)rwρ|W=−1+2ρ,−2ρ+2+n,−2ρ+1+n,if1≤ρ≤n−22,−1+2ρ,4,1,ifn2≤ρ≤2+n2,5−2ρ+2n,−n+2+2ρ,−1−n+2ρ,if4+n2≤ρ≤n,3,n+2,1+n,ifρ=1+n.
Representation of the verticesvρ where 1≤ρ≤1+n is(9)rvρ|W=2ρ+1,−2ρ+n,−2ρ+1+n,if1≤ρ≤n−22,n+1,2,1,ifρ=n2,5−2ρ+2n,2−n+2ρ,−n+1+2ρ,if2+n2≤ρ≤n,1,n,n+1,ifρ=1+n.
Representation of the verticesyρ where 1≤ρ≤n is(10)ryρ|W=2ρ,−2ρ+1+n,−2ρ+n,if1≤ρ≤n−22,n,3,0,ifρ=n2,4−2ρ+2n,−n+3+2ρ,−n+2ρ,if2+n2≤ρ≤n.
The distance-vector representations are distinct for all the vertices ofSNen. So, W is the RS. Hence, βSNen≤3. Now, in order to prove that βSNen≥3, suppose contrary that βSNen=2, and according to Lemma 3, we have the following possibilities:(1)
LetW=xi,xj⊂VSNen for 0≤i<j≤n+2/2; then, ADvn,wn|W=0,0. So, W is not the RS.(2)
LetW=ui,uj⊂VSNen for 1≤i<j≤n+2/2; then, ADvn,wn|W=0,0. So, W is not the RS.(3)
LetW=xi,xj⊂VSNen for 0≤i≤n/2 and n+2/2≤j≤n+1; then, we have the following subcases:(a) Whenn=4:(i)
ADv4,w4|W=0,0 for j≠4.(ii)
ADv1,w2|W=0,0 for i≠1 and j=4.(iii)
ADu1,u2|W=0,0 for i=1 and j=4.(b)
Whenn≥6:(i)
ADvn,wn|W=0,0 for j≠n.(ii)
ADun,vn|W=0,0 for 0≤i≤n/2−2 and j=n.(iii)
ADv1,w2|W=0,0 for n/2−1≤i≤n/2 and j=n.So,W is not the RS.(4)
LetW=ui,uj⊂VSNen for 1≤i≤n/2<j≤n+1; then, we have the following subcases:(a) Whenn=4:(i)
ADv4,w4|W=0,0 for j=3.(ii)
ADv1,w1|W=0,0 for i=1 and j=4.(iii)
ADw1,w2|W=0,0 for i=2 and j=4.(iv)
ADu4,v4|W=0,0 for i=1 and j=5.(v)
ADx1,x2|W=0,0 for i=2 and j=5.(b) Whenn=6:(i)
ADv6,w6|W=0,0 for n/2+1≤j≤n−1.(ii)
ADv2,w2|W=0,0 for i=1 and j=6.(iii)
ADx1,x2|W=0,0 for i=2 and j=6.(iv)
ADv1,w2|W=0,0 for i=3 and j=6.(v)
ADu6,v6|W=0,0 for i≠3 and j=7.(vi)
ADx2,x3|W=0,0 for i=3 and j=7.(c) Whenn≥8:(i)
ADvn,wn|W=0,0 for n/2+1≤j≤n−1.(ii)
ADvn/2−1,wn/2−1|W=0,0 for 1≤i≤n/2−2 and j=n.(iii)
ADv1,w2|W=0,0 for n/2−1≤i≤n/2 and j=n.(iv)
ADun,vn|W=0,0 for i≠n/2 and j=n+1.(v)
ADxn/2−1,xn/2|W=0,0 for i=n/2 and j=n+1.So,W is not the RS.(5)
LetW=xi,uj⊂VSNen for 0≤i≤n/2 and 1≤j≤n+2/2; then, ADvn,wn|W=0,0. So, W is not the RS.(6)
LetW=xi,vj⊂VSNen for 0≤i≤n/2 and 1≤j≤n/2; then, we have the following subcases:(i)
ADvn+1,wn+1|W=0,0 for i≠n/2.(ii)
ADun/2+1,vn/2|W=0,0 for i=n/2 and j≠n/2.(iii)
ADun/2,un/2+1|W=0,0 for i=n/2 and j=n/2.So,W is not the RS.(7)
LetW=ui,vj⊂VSNen for 1≤i≤n+2/2 and 1≤j≤n/2; then, we have the following subcases:(i)
ADun+1,wn+1|W=0,0 for i≠n+2/2.(ii)
ADun/2+2,vn/2+1|W=0,0 for i=n+2/2.So,W is not the RS.(8)
LetW=xi,yj⊂VSNen for 0≤i≤n/2 and 1≤j≤n/2; then, we have the following subcases:(i)
ADun+1,wn+1|W=0,0 for i≠n/2 and j≠n/2.(ii)
ADun/2,vn/2|W=0,0 for i=n/2 and j≠n/2.(iii)
ADun,vn|W=0,0 for i=0 and j=n/2.(iv)
ADvn/2,wn/2|W=0,0 for 1≤i≤n−2/2 and j=n/2.(v)
ADun/2,un/2+1|W=0,0 for i=n/2 and j=n/2.So,W is not the RS.(9)
LetW=ui,wj⊂VSNen for 1≤i≤n+2/2 and 1≤j≤n+2/2; then, we have the following subcases:(i)
ADun+1,wn+1|W=0,0 for i≠n+2/2 and j≠n+2/2.(ii)
ADvn,wn|W=0,0 for i=n+2/2 and 1≤j≤n−2/2.(iii)
ADxn−2/2,yn+2/2|W=0,0 for i=n+2/2 and j=n/2.(iv)
ADun,vn|W=0,0 for 1≤i≤n−2/2 and j=n+2/2.(v)
ADxn+2/2,yn−2/2|W=0,0 for i=n/2 and j=n+2/2.(vi)
ADxn/2,xn/2+1|W=0,0 for i=n+2/2 and j=n+2/2.So,W is not the RS.(10)
LetW=ui,yj⊂VSNen for 1≤i≤n+2/2 and 1≤j≤n/2; then, we have the following subcases:(i)
ADun+1,wn+1|W=0,0 for i≠n+2/2 and j≠n/2.(ii)
ADun/2,vn/2|W=0,0 for i=n+2/2 and j≠n/2.(iii)
ADvn/2,wn/2|W=0,0 for 1≤i≤n−2/2 and j=n/2.(iv)
ADxn/2,xn/2+1|W=0,0 for n/2≤i≤n+2/2 and j=n/2.So,W is not the RS.
We deduce to contradict in all the possibilities. So, there is no RS with cardinality 2. This shows thatβSNen≥3. Hence, βSNen=3.Now, the following theorem presented the exact value of the FTMD of the subdivision graph of the necklace graph.Theorem 3.
For any integern≥3, we have β′SNen=4.Proof.
Following are the cases to calculate required results:Case 3.
(whenn is odd).
TakeW′=x0,un+1/2,vn+1/2,wn+1/2⊆VSNen for all odd integers n≥3. We need to prove that W′ is the FTRS for the graph SNen. To prove this, we give distance-vector representations of every vertex in SNen. Representation of the vertices xρ where 0≤ρ≤1+n is(11)rxρ|W′=0,n,n+2,n,ifρ=0,2ρ,−2ρ+n,21−ρ+n,21−ρ+n,if1≤ρ≤n−12,1+n,1,1,3,ifρ=1+n2,−2ρ+4+2n,2ρ−n,−n+2ρ,−n+21+ρ,if3+n2≤ρ≤n,2,n+2,2+n,n+2,ifρ=1+n.
Representation of the verticesuρ where 1≤ρ≤1+n is(12)ruρ|W′=−1+2ρ,−2ρ+1+n,−2ρ+3+n,−2ρ+3+n,if1≤ρ≤n−12,n,0,2,4,ifρ=1+n2,5−2ρ−n,−n−1+2ρ,−1+2ρ−n,−n+1+2ρ,if3+n2≤ρ≤1+n.
Representation of the verticeswρ where 1≤ρ≤1+n is(13)rwρ|W′=−1+2ρ,−2ρ+3+n,−2ρ+3+n,−2ρ+n+1,if1≤ρ≤n−12,n,4,2,0,ifρ=1+n2,−2ρ+5+2n,−n+1+2ρ,−n−1+2ρ,−1−n+2ρ,if3+n2≤ρ≤1+n.
Representation of the verticesvρ where 1≤ρ≤1+n is(14)rvρ|W′=2ρ+1,−2ρ+1+n,−2ρ+3+n,−2ρ+n+1,if1≤ρ≤n−12,2+n,2,0,2,ifρ=1+n2,5−2ρ+2n,−n+1+2ρ,−n+1+2ρ,−n+2ρ+1,if3+n2≤ρ≤n,1,n+1,3+n,1+n,ifρ=1+n.
Representation of the verticesyρ where 1≤ρ≤n is(15)ryρ|W′=2ρ,−2ρ+2+n,−2ρ+2+n,−2ρ+n,if1≤ρ≤n−12,1+n,3,1,1,ifρ=1+n2,−2ρ+4+2n,−n+2+2ρ,2ρ−n,−n+2ρ,if3+n2≤ρ≤n.
The distance-vector representations are distinct for all the vertices ofSNen. So, W′ is the RS. We can also verify that, for every x,y∈VSNen, at least two elements in the 4-vector ADx,y|W′ are nonzero. So, the RS W′ becomes a FTRS. This shows that β′SNen≤4. By using Lemma 1 and Theorem 2, we have β′SNen≥4. Hence, β′SNen=4.Case 4.
(whenn is even).
TakeW′=x0,xn/2,vn+4/2,yn/2⊆VSNen for all even integers n≥4. Representation of the vertices xρ where 0≤ρ≤1+n is(16)rxρ|W′=0,n,1+n,n,ifρ=0,2ρ,−2ρ+n,−2ρ+5+n,−2ρ+2+n,if1≤ρ≤n2,2+n,2,3,4,ifρ=2+n2,−2ρ+4+2n,−n+2ρ,−n−3+2ρ,−n+2+2ρ,if4+n2≤ρ≤n,2,n+2,−1+n,2+n,ifρ=1+n.
Representation of the verticesuρ where 1≤ρ≤1+n is(17)ruρ|W′=1,−1+n,n+2,1+n,ifρ=1,−1+2ρ,−2ρ+1+n,−2ρ+6+n,−2ρ+3+n,if2≤ρ≤n2,1+n,1,4,3,ifρ=2+n2,1+n,3,2,5,ifρ=4+n2,5−2ρ+2n,−n−1+2ρ,−n−4+2ρ,−n+1+2ρ,if6+n2≤ρ≤1+n.
Representation of the verticeswρ where 1≤ρ≤1+n is(18)rwρ|W′=1,1+n,2+n,−1+n,ifρ=1,−1+2ρ,−2ρ+3+n,−2ρ−3+n,−2ρ+n+1,if2≤ρ≤n2,1+n,3,4,1,ifρ=2+n2,1+n,5,2,3,ifρ=4+n2,−2ρ+5+2n,−n+1+2ρ,−4−n+2ρ,−1−n+2ρ,if6+n2≤ρ≤1+n.
Representation of the verticesvρ for n=4 where 1≤ρ≤5 is(19)rvρ|W′=1+2ρ,−2ρ+5,−2ρ+4,−2ρ+5,if1≤ρ≤2,7,3,4,3,ifρ=3,5,5,0,5,ifρ=4,1,5,4,5,ifρ=5.
Representation of the verticesvρ for n>4 where 1≤ρ≤1+n is(20)rvρ|W′=1+2ρ,1−2ρ+n,−4−2ρ+2n,1−2ρ+n,if1≤ρ≤n2,3+n,3,4,3,ifρ=2+n2,1+n,5,0,5,ifρ=4+n2,5−2ρ+2n,−n+1+2ρ,−n−2+2ρ,−n+1+2ρ,if6+n2≤ρ≤n,1,n+1,n,1+n,ifρ=1+n.
Representation of the verticesyρ where 1≤ρ≤n is(21)ryρ|W′=2ρ,−2ρ+2+n,−2ρ+5+n,−2ρ+n,if1≤ρ≤n2,2+n,4,3,2,ifρ=2+n2,−2ρ+4+2n,−n+21+ρ,−n−3+2ρ,−n+2ρ,if4+n2≤ρ≤n.
The distance-vector representations are distinct for all the vertices ofSNen. So, W′ is the RS. We can also verify that, for every x,y∈VSNen, at least two elements in the 4-vector ADx,y|W′ are nonzero. So, the RS W′ becomes a FTRS. This shows that β′SNen≤4. By using Lemma 1 and Theorem 2, we have β′SNen≥4. Hence, β′SNen=4.


## 3. The Fault-Tolerant Metric Dimension for the Subdivision of the Prism Graph

The prism graphYn is Cartesian product graph Cn×P2, where Cn is the cycle graph of order n and P2 is a path of order 2. The prism graph Yn consists of 4-sided faces and n-sided faces with vertex set VYn=xk,yk;1≤k≤n as shown in Figure 4.Figure 4
Prism graph.Yn.Now, to computeβ′SYn, we need to convert the prism graph into its subdivision graph. The subdivision graph of the prism graph SYn is shown in Figure 2.The known result of the MD of the subdivision graph of the prism graph is given in the following theorem.Theorem 4 (see [26]).
For any integern≥4, we have βSYn=3.Here, we will find the exact value ofβ′SYn, which is presented in the following theorem.Theorem 5.
For any integern≥3, we have β′SYn=4.Proof.
Following are the cases to compute required results:Case 5.
(whenn is even).
TakeW′=x1,x2,xn+2/2,xn+4/2⊆VSYn for all even integers n≥4. We need to prove that W′ is the FTRS for the graph SYn. To prove this, we give distance-vector representations of every vertex in SYn. Representation of the vertices xρ where 1≤ρ≤n is(22)rxρ|W′=0,2,n,−2+n,ifρ=1,−21−ρ,−22−ρ,−2ρ+2+n,−2ρ+4+n,if2≤ρ≤2+n2,−2ρ+2+2n,−2ρ+4+2n,−2−n+2ρ,−4−n+2ρ,if4+n2≤ρ≤n.
Representation of the verticesuρ where 1≤ρ≤n is(23)ruρ|W′=1,1,−1+n,−1+n,ifρ=1,2ρ−1,−3+2ρ,−2ρ+n+1,−2ρ+3+n,if2≤ρ≤n2,−1+n,−1+n,1,1,ifρ=2+n2,−2ρ−n+1,−2ρ+3+2n,−n−1+2ρ,−n−3+2ρ,if4+n2≤ρ≤n.
Representation of the verticesvρ where 1≤ρ≤n is(24)rvρ|W′=1,3,1+n,−1+n,ifρ=1,−1+2ρ,−3+2ρ,−2ρ+3+n,−2ρ+5+n,if2≤ρ≤2+n2,−2ρ−n+3,−2ρ+5+2n,−1−n+2ρ,−n−3+2ρ,if4+n2≤ρ≤n.
Representation of the verticesyρ where 1≤ρ≤n is(25)ryρ|W′=2,4,2+n,n,ifρ=1,2ρ,−21−ρ,−2ρ+4+n,−2ρ+6+n,if2≤ρ≤2+n2,−2ρ−2−n,−2ρ−3−n,−n+2ρ,−2−n+2ρ,if4+n2≤ρ≤n.
Representation of the verticeswρ where 1≤ρ≤n is(26)rwρ|W′=3,3,1+n,1+n,ifρ=1,1+2ρ,−1+2ρ,−2ρ+3+n,−2ρ+5+n,if2≤ρ≤n2,1+n,1+n,3,3,ifρ=2+n2,−2ρ+3+2n,−2ρ+5+2n,−n+1+2ρ,−n−1+2ρ,if4+n2≤ρ≤n.
The distance-vector representations are distinct for all the vertices ofSYn. So, W′ is the RS. We can also verify that, for every x,y∈VSYn, at least two elements in the 4-vector ADx,y|W′ are nonzero. So, the RS W′ becomes a FTRS. This shows that β′SYn≤4. By using Lemma 1 and Theorem 4, we have β′SYn≥40,1. Hence, β′SYn=4.Case 6.
(whenn is odd).
Forn=3, take W′=x1,x2,y1,y2⊆VLY3. It is quite simple to check that W′ is a FTRS.
TakeW′=x1,x2,y1,y2⊆VLYn for all odd integers n≥5. Representation of the vertices xρ where 1≤ρ≤n is(27)rxρ|W′=0,2,2,4,ifρ=1,−21−ρ,−22−ρ,2ρ,−21−ρ,if2≤ρ≤1+n2,−1+n,n−1,1+n,1+n,ifρ=3+n2,−2ρ−1−n,−2ρ−2−n,−2ρ+4+2n,−2ρ−3−n,if5+n2≤ρ≤n.
Representation of the verticesuρ where 1≤ρ≤n is(28)ruρ|W′=1,1,3,3,ifρ=1,2ρ−1,−3+2ρ,2ρ+1,−1+2ρ,if2≤ρ≤1+n2,−2ρ−n+1,−2ρ+3+2n,−2ρ+3+2n,−2ρ−n+5,if3+n2≤ρ≤n.
Representation of the verticesvρ where 1≤ρ≤n is(29)rvρ|W′=1,3,1,3,ifρ=1,−1+2ρ,−3+2ρ,2ρ−1,−3+2ρ,if2≤ρ≤1+n2,n,n,n,n,ifρ=3+n2,−2ρ−n+3,−2ρ+5+2n,−2ρ+3+2n,−2ρ−n+5,if5+n2≤ρ≤n.
Representation of the verticesyρ where 1≤ρ≤n is(30)ryρ|W′=2,4,0,2,ifρ=1,2ρ,−21−ρ,−2+2ρ,−22−ρ,if2≤ρ≤1+n2,1+n,n+1,n−1,−1+n,ifρ=3+n2,−2ρ+4+2n,−2ρ−3−n,−2ρ+2+2n,−2ρ+4+2n,if5+n2≤ρ≤n.
Representation of the verticeswρ where 1≤ρ≤n is(31)rwρ|W′=3,3,1,1,ifρ=1,1+2ρ,−1+2ρ,2ρ−1,−3+2ρ,if2≤ρ≤1+n2,−2ρ−n+3,−2ρ+5+2n,−2ρ+1+2n,−2ρ−n+3,if3+n2≤ρ≤n.
The distance-vector representations are distinct for all the vertices ofSYn. So, W′ is the RS. We can also verify that, for every x,y∈VSYn, at least two elements in the 4-vector ADx,y|W′ are nonzero. So, the RS W′ becomes a FTRS. This shows that β′SYn≤4. By using Lemma 1 and Theorem 4, we have β′SYn≥4. Hence, β′SYn=4.


## 4. Conclusion

In this paper, we have studied, for the first time, the FTMD of the subdivision graph of a graph. We have found that the FTMD of the subdivision graphs of the necklace and prism graphs is exactly greater than one of their metric dimensions.



---

*Source: 5784800-2022-02-18.xml*