# Fault-Tolerant Metric Dimension of Generalized Wheels and Convex Polytopes

Authors: Zhi-Bo Zheng; Ashfaq Ahmad; Zaffar Hussain; Mobeen Munir; Muhammad Imran Qureshi; Imtiaz Ali; Jia-Bao Liu
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

For a graphG, an ordered set S⊆VG is called the resolving set of G, if the vector of distances to the vertices in S is distinct for every v∈VG. The minimum cardinality of S is termed as the metric dimension of G. S is called a fault-tolerant resolving set (FTRS) for G, if S\v is still the resolving set ∀v∈VG. The minimum cardinality of such a set is the fault-tolerant metric dimension (FTMD) of G. Due to enormous application in science such as mathematics and computer, the notion of the resolving set is being widely studied. In the present article, we focus on determining the FTMD of a generalized wheel graph. Moreover, a formula is developed for FTMD of a wheel and generalized wheels. Recently, some bounds of the FTMD of some of the convex polytopes have been computed, but here we come up with the exact values of the FTMD of two families of convex polytopes denoted as Dk for k≥4 and Qk for k≥6. We prove that these families of convex polytopes have constant FTMD. This brings us to pose a natural open problem about the existence of a polytope having nonconstant FTMD.


---

## Body

## 1. Introduction

Computer networks and other similar systems can be given design of graphs in which vertices are the representor of nodes and edges as a medium of connection between them. The location of fault in the computer network is the vertex of a graph. This idea to identify each vertex in the network was initially given by Slater in [1] and then by Harary and Melter in [2] to control the fault in a better way. Therefore, the concepts of locating numbers and locating sets were developed. In fact, the actual terminology appeared way back by Blumenthal [3] for standard Euclidean spaces. However, not many researchers were forced to think about these ideas because of linear continuum nature of these spaces.The resolving set and ideas, pretty similar to it, are contributing in diverse areas today merely because of their usage in discrete nature. These ideas are utilized to recognize nodes in a network, connected joins in graphs, mastermind games [4], strategies for the network discovery, combinatorial optimization, applications of pattern recognition, pharmaceutical chemistry, image processing, and game theory. A collection of points can be identified by finding the distance from all nodes in a network or graph. Thus, the problem of robot navigation may be solved by finding a minimal set of fixed vertices. Such minimal sufficiently large set is a resolving set of the graph. The corresponding cardinality is termed as metric dimension.For a connected, simple graphG, metric dG:VG×VG⟶ℕ∪0 is the distance between x and y and is denoted by dGx,y. Let W=w1,w2,⋯,wk⊆VG be an ordered set, and let v∈VG. Then, rv|W is the representation of v with respect to W and is the k-tuple dv,w1,dv,w2,⋯,dv,wk. If rv|W are distinct for distinct vertices of G, then we say W is a resolving set for G, see [5]. A resolving set with minimum cardinality is a basis of G, and its cardinality is termed as the metric dimension of G, denoted by βG.Buczkowski et al. computed the metric dimension of wheelWn and proved that ⌊2n+2/5⌋ for n≥7 [5]. In [6], Hernando et al. proved that for fan, the metric dimension is ⌊2n+2/5⌋ for n≥7, and for Jahangir graphs J2n, Tomescu and Javaid proved that ⌊2n/3⌋ for all n≥4, see [7]. In [8, 9], the authors proved some results about the metric dimension of regular graphs. In [10], the metric dimension for a flower graph is computed by the authors. In [11], Chartrand et al. proved that a metric dimension is 1 iff graph is a path. In 2014, the authors in [12] computed the metric dimension for the generalized wheel graph. Ali et al. [13], in 2012, and Munir et al. [14], in 2017, studied about the metric dimension of Möbius ladders. For unicyclic graphs, Poisson and Zhang found metric dimension in [15]. If for a family Gnn≥1 of connected graphs, where exists a constant C>0 such that βGn≤C for all n≥1, then the family of graphs is said to have bounded metric dimension; otherwise, it has unbounded metric dimension. If all graphs of a family have the same metric dimension (means do not depend on n), then that family is called a family with constant metric dimension [16]. For further study, one can see [17–26].Recent advancement in the concept of metric dimension has paved a path for a new related idea known as fault tolerance. Suppose a network consists ofn processing units. To form a fault-tolerant self-stable system, it is essential that if any single unit becomes fail, another chain of units (excluding the faulty unit) can replace the originally used chain. So, the design of this fault-tolerance empowers the system to continue working, possibly at a reduced level and opposed to flop totally.A resolving setS´ is contemplate to be fault-tolerant if S´\v is also a resolving set, ∀v∈S´, and consequently, the minimum cardinality of such S´ is termed as FTMD, denoted by β′G. If the order of S´ is equal to β′G, then it is called a fault-tolerant metric basis. FTMD is constant for a family G of connected graphs if it is not dependent on any choice of the member of that family. Fault-tolerant designs are successfully used in computer sciences and engineering [27]. The study of fault-tolerant sets was inaugurated by Slater in [28]. Hernando et al. developed the concept of an FTMD in [29]. They studied the FTMD of trees. They also proved a very important result in the form of upper bound irrespective of the choice of graph which is given as β′G≤βG1+2.5βG−1. Javaid et. al. in [30, 31] studied fault-tolerance in resolvability, and also, they computed FTMD of few classes of graphs. It is not difficult to conclude that β′G≥βG+1. Few more results were found by Shabbir and Zamfirescu in [32] about triangular lattice networks.In this article, we considered families of convex polytopes and studied the FTMD for them. A convex polytope is the convex-hull of an finite set in any Euclidean space. These are significant graphs and hence have been under discussion from many years. For instance, Baca in [33, 34] computed labellings and magic of convex polytopes. Nazeer et al. computed the formulae for the average eccentricity, eccentricity, center, and periphery for the convex polytopes in [35]. In [21], Imran et al. found that the metric dimension is constant for convex polytopes Sk, Tk, Qk, and Dk. In this article, we take a step further and prove that Dk and Qk have constant FTMD. We also discuss the FTMD of multilevel wheel and classical wheel graphs.


## 2. Main Results

In this section, we put together our main results. At first, we prove that FTMD ofDk is 4. Then, we move towards the case of Qk. In both cases, we use double inequality of sets. In the end, we compute the FTMD of multilevel wheel.


### 2.1. Fault-Tolerant Metric Dimension of the Graph ofDk and Qk

LetAk denote the antiprism graph. The graph Ak is obtained using two regular k-gones say P and P´ with the vertices u1,u2,⋯,uk and z1,z2,⋯,zk, respectively, in anticlockwise. We join any vertex up of P with the vertices zp and zp+1 of P´ by edges for p=1,2,⋯,k. The graph of the convex polytope Dk is formed [33], by the dual graph of Ak consisting of the vertices u1,u2,u3,⋯,uk,x1,x2,x3,⋯,xk;y1,y2,y3,⋯,yk; and z1,z2,z3,⋯,zk. It consists of 5-sided and k-sided faces. For compete details, see Figure 1.Figure 1
Graph ofDk.The convex polytopeQk defined in [34] has faces of 3 sides, 4 sides, 5 sides, and n-sides. The vertex set for the graph of the convex polytope Qk is the same as that of the convex polytope Dk, and also, EQk=EDk∪xpxp+1:1≤p≤k.Let us call the verticesup,1≤p≤k, xp,1≤p≤k, yp,1≤p≤k, and zp,1≤p≤k as the inner vertices, the middle vertices, the interior vertices, and the outer vertices, respectively. The cycles induced by up,1≤p≤k, xp,1≤p≤k, and zp,1≤p≤k are the inner cycle, the middle cycle, and the outer cycle respectively, as shown in Figure 2.Figure 2
Graph ofQk.Theorem 1.
For both type of convex polytopesDk and Qk, β′=4 for k≥6, where k is an integer.Proof.
Case I:k is even: let k=2n; n∈Z+, and n≥3. Let F=u1,u2,un+1,un+2. We shall prove that F is a fault-tolerant metric basis for Dk and Qk in the present case. We prove that the metric representations of all vertices of Dk and Qk with respect to F are distinct in at least two coordinates. We call uk+1, xk+1, yk+1, and zk+1 as the vertices of inner cycle, the inner vertices, the outer vertices, and the vertices of outer cycle, respectively.The metric representations of vertices lying on the inner cycle are(1)rup|F=−1+p,−2+p,n+1−p,n+2−p,if3≤p≤n,2n+1−p,2n+2−p,p−1−n,p−2−n,ifn+3≤p≤2n.The metric representations of vertices belonging to inner vertices are(2)rxp|F=1,2,n+1,n,ifn=1,p,−1+p,n+2−p,n+3−p,if2≤p≤n+1,2n+2−p,2n+3−p,p−n,p−1−n,ifn+2≤p≤2n.The metric representations of vertices belonging to outer vertices are(3)ryp|F=2,2,n+1,n+1,ifp=1,p+1,p,n+2−p,n+3−p,if2≤p≤n,n+1,n+1,2,2,ifp=n+1,2n+2−p,2n+3−p,p+1−n,p−n,ifn+2≤p≤2n.The metric representations of vertices lying on the outer cycle are(4)rzp|F=3,3,2+n,2+n,ifp=1,2+p,1+p,3+n−p,4+n−p,if2≤p≤n,n+2,n+2,3,3,ifp=n+1,2n+3−p,2n−p+4,p−n+2,p−n+1,ifn+2≤p≤2n.These representations are distinct in at least two coordinates. So,F is an FTRS. Therefore, for both Dk and Qk, β′≤4. Since for both Dk and Qk, β=3 as proved in [21], so β′>3. Hence, β′=4 when k is even.Case II:k is an odd integer: let k=2n+1 where n∈Z+ and n≥3, and F=u1,u2,un+1,un+2. We shall prove that F is a fault-tolerant metric basis for Dk and Qk in the present case. We prove that the metric representations of all vertices of Dk and Qk with respect to F are distinct in at least two coordinates.
The metric representations of vertices lying on the inner cycle are(5)rup|F=−1+p,−2+p,1+n−p,2+n−p,if3≤p≤n,2n+2−p,2n+3−p,p−n−1,p−n−2,ifn+3≤p≤2n+1.
The metric representations of inner vertices are(6)rxp|F=1,2,n+1,n+1,ifp=1,p,−1+p,2+n−p,3+n−p,if2≤p≤n+1,n+1,n+1,2,1,ifp=n+2,2n−p+3,2n−p+4,p−n,p−n−1,ifn+3≤p≤2n+1.
The metric representations of outer vertices are(7)ryp|F=2,2,n+1,n+2,ifp=1,p+1,p,n−p+2,n−p+3,if2≤p≤n,n+2,n+1,2,2,ifp=n+1,2n−p+3,2n−p+4,p−n+1,p−n,ifn+2≤p≤2n+1.
The metric representations of vertices on the outer cycle are(8)rzp|F=3,3,2+n,n+3,ifp=1,2+p,1+p,n+3−p,n+4−p,if2≤p≤n,n+3,n+2,3,3,ifp=n+1,2n−p+3,2n−p+4,p−n+2,p−n+1,ifn+2≤p≤2n+1.
These representations are distinct in at least two coordinates. So,F is an FTRS. Therefore, for both Dk and Qk, β′≤4. Since for both Dk and Qk, β=3 as proved in [21], so β′>3. Hence, β′=4 when k is odd.


### 2.2. Fault Tolerance in Metric Dimension of Multilevel Wheel

In this part, we focus on the FTMD of multilevel wheelWn,m. An m wheel graph of size n is defined as follows: an m wheel graph of size n can be composed of mCn+K1. It consists of m cycles of size n, where the vertices of the m cycles are all connected to a common hub. Thus, Wn,m has nm+1 vertices, the center, and n rim vertices and has diameter 2. Figure 3 represents the graph of W8,m.Figure 3
Graph ofW8,m.A classical wheel graph is simply a specialized wheel with a single level denoted asWn,1 or simply Wn. Here, we give the graph of W8,1 in Figure 4.Figure 4
A graph ofW8,1 wheel.We do not include the central vertex in the representation of the above graphW8,1. In the above graph, the vertices of the graph G are VG=v1,v2,v3,v4,v5,v6,v7,v8. Now, consider the resolving sets R1 = v2,v4,v6, R2 = v2,v6,v8, R3 = v2,v4,v8, and R4 = v4,v6,v8. For R1 = v2,v4,v6, it is easy to see that rv1/R1 = 1,2,2, rv2/R1 = 0,2,2, rv3/R1 = 1,1,2, rv4/R1 = 2,0,2, rv5/R1 = 2,1,1, rv6/R1 = 2,2,0, rv7/R1 = 2,2,1, and rv8/R1 = 2,2,2. Since the vertices of G have distinct representations with respect to R1, R1 is a resolving set. Since metric dimension of a wheel graph W8 is 3, R1 is a basis for G because it has metric dimension 3. Similarly, R2, R3, and R4 are also basis for G with metric dimension 3. Now, R5 = R1∪R2∪R3∪R4 or R5 = v2,v4,v6,v8.We see thatR5\v is also a resolving set for each v in R5. As βW8,1 of the above example is 3, therefore, β,W8,1=4. Hence, R5 is a fault-tolerant metric basis with β,W8,1=4, so R5 is an FTMS.IfB´ is a resolving set of the graph G, which contains two or more vertices of G, and we suppose that the vertices of B´=vj1,vj2,⋯,vjr, so the j1<j2<⋯<jr. We shall say that the vertices vja, vja+1 for i=1,2,⋯,r−1, and vjr, vj1 are neighboring vertices. Now, the vertices lying between these neighboring vertices are referred to as the gap of B´ and the number of vertices in a gap will be referred to as the size of the gap. If B´ is t, then it has t gapes, and some of which may be empty. For example, the gap between v2andv4 in Figure 4 is 1 because there is only one vertex v3 in between v2 and v4. Now, let B is an FTMS of Wn,m. If we do not include the central vertex, then we make the following two conditions:(1)
Ifn is even, then every gap of B contains exactly one vertex. If a gap contains zero vertex, then B\v does not remain as an FTMS. Similarly, if a gap contains two or more vertices, then again B\v does not remain as an FTMS, which is a contradiction.(2)
Ifn is odd, then every gap of B contains exactly one vertex except for one gap which contains zero vertex. If more than one gap contains zero vertex, then B\v does not remain as an FTMS. Similarly, if a gap contains two or more vertices, then again B\v does not remain as an FTMS, which is a contradiction.Our aim in this section is to compute the FTMD of wheelWn and generalize the wheel graph Wn,r. In [5], it was shown that dimWn=2n+5/2, for every n≥7. Now, suppose that B′ is any fault-tolerant metric basis of Wn. We observe the following results in the form of lemmas and theorems.


#### 2.2.1. Lemmas

Lemma 1.
Ifn is even and n≥8, then every gap of B′ (fault-tolerant basis) contains exactly one vertex.Proof.
(i)
Suppose on the contrary, there exists a gap which contains two vertices and at least one of its neighboring gaps contains one vertex. Then,∃vi,vi+1,vi+2,vi+3,vj (where vj is neighboring vertex of vi+3 and contains one vertex), such that vi,vi+3, vj belong to B′. Then, by B′\vi+3, we obtained rvi+2/B′ = rvi+3/B′ = 2,2,2,⋯,2, which is a contradiction.(ii)
Now, again on the contrary, there exists a gap which contains two vertices and its neighboring gaps are empty. Then, there exist verticesvi,vi+1,vi+2,vi+3,vi+4,vi+5,vj (where vj is neighboring vertex of vi+5 and is empty while another neighboring gap of vi is not empty), such that vi,vi+1,vi+4,vi+5,vj belong to B′. Then, by B′\vi, we have rvi/B′ = rvi+2/B′ = 1,2,2,⋯,2, which is a contradiction.(iii)
Now, again on the contrary, there exists a gap which contains two vertices and its neighboring gaps are empty. Then, there exist verticesvi,vi+1,vi+2,vi+3,vi+4,vi+5,vi+6,vi+7. Then, there exists vj, any other vertex of B′, such that vi,vi+1,vi+2,vi+5,vi+6,vi+7,vj belong to B′. Then, by B′\vj, we have rvn−1/B′ = rvn−2/B′ = 2,2,2,⋯,2, which is a contradiction.Lemma 2.
Ifn is odd and n≥7, then every gap of B′ (fault-tolerant basis) contains exactly one vertex except for one gap which is empty.Proof.
Suppose on the contrary, there exists a gap which contains two vertices. Then,∃vi,vi+1,vi+2,vi+3,vj (where vj is neighboring vertex of vi+3), such that vi,vi+3, vj belong to B′. Then, by B′\vj, we have rvi+2/B′ = rvi+4/B′, which is a contradiction.Lemma 3.
The resolving set ofCn of the type B′ = v1,v3,v5,……vn−1 or B′ = v2,v4,v6,……vn is fault-tolerant metric basis.Proof.
We see from Lemmas1 and 2 that B′ can be an FTMS because for each v in B′, the set B′\v is a resolving set. Now, we see that the set B′\v1,v3 or B′\v2,v4 is not a resolving set, which is a contradiction. Hence, B′ is a fault-tolerant metric basis.Lemma 4.
IfC1 and C2 denote the vertices of circle 1 and circle 2, respectively, then fault-tolerant metric basis for C1 and C2 is the same.Proof.
LetC1 and C2 denote the set of vertices of circle 1 and circle 2, respectively. Let vi∈C1 and wi∈C2. Now, dvi,wi=dwi,vi=2. Also, there does not exist any vi belongs to C1 such that by B′\vi, we get rvj/B′ = rvr/B′ = (2, 2, 2, ⋯, 2). Similarly, there does not exist any wi belongs to C2 such that by B′\vi, we get rwj/B′ = rwr/B′ = (2, 2, 2, ⋯, 2). In the same way, we can show that all levels have the same FTMS.
Now, we move towards the main results of this section.Theorem 2.
Ifn≥7 and m≥1, then we have β,Wn,m=mn/2.Proof.
(whenm=1).
We divide the proof into the following two cases based on parity ofn.(i)
Case I:. when n is even: if n is even, then we can write n=2k+4, where k≥2 and β,Wn,1=⌊n/2⌋=k+2. Then, B=V2i,1≤i≤n/2 is an FTMS as it satisfies conditions 1 and 2.(ii)
Case II: when n is odd: when n is odd, then we may write n=2k+3, where k≥2 and β,Wn,1=n/2=k+2. B=V1,V2i,1≤i≤n−1/2. It is an FTMS as it satisfies conditions 1 and 2. It follows from the above discussion that β,Wn,1=n/2.
Next, we show thatβ,Wn,1=n/2 is the cardinality of FTMS. From Case 1 and Case 2, one can note that B can be an FTMS because for each v in B, the set B\v is a resolving set. Now, we show that B is an FTMS. Suppose that B is not an FTMS, then there exists vertex v in B such that C = B\v is an FTMS. Since C is an FTMS as each v in C, C\v should be a resolving set. However, C\v is not a resolving set which is a contradiction. Hence, B is an FTMS.Proof.
(whenm=2).
(i)
Case I: when n is even: when n is even, then we may write n=2k+4, where k≥2 and β,Wn,2=2n/2 = 2 (k + 2). Then, B=v2i,w2i,1≤i≤n/2 is an FTMS as it satisfies conditions 1 and 2.(ii)
Case II: when n is odd: then, we may write n=2k+3, where k≥2 and β,Wn,2=2n/2 = 2 (k + 2). Then, B=v1,v2i,w1,w2i,1≤i≤n−1/2 is an FTMS as it satisfies both conditions 1 and 2. It follows from the above discussion that β,Wn,2=2n/2.
Next, we show thatβ,Wn,2=2n/2 is the cardinality of the FTMS. We see from Case 1 and Case 2 that B can be an FTMS because for each v in B, the set B\v is a resolving set. We show that B is an FTMS. Suppose on the contrary that B is not an FTMS, then there exists a v in B such that C = B\v is an FTMS. Now, C is an FTMS. Therefore, for each v in C, C\v should be a resolving set. However, C\v is not a resolving set which is a contradiction. Hence, B is an FTMS.Proof.
(whenm≥3). We shall prove this case by mathematical induction.
For level 1, we havem=1 and then β′Wn,1=n/2. For level 2, i.e., m=2, we have β′Wn,2=2n/2. Now, we suppose that the assertion is true for level k, i.e.,(9)β′Wn,k=kn/2·1.
We shall show that it is true form=k+1. We have β′Wn,k+1=β′Wn,k+β′Wn,1.
Then,(10)β′Wn,k+1=kn2+n2,β′Wn,k+1=k+1n2.
Hence, the given statement is true for all positive integersm≥3.


## 2.1. Fault-Tolerant Metric Dimension of the Graph ofDk and Qk

LetAk denote the antiprism graph. The graph Ak is obtained using two regular k-gones say P and P´ with the vertices u1,u2,⋯,uk and z1,z2,⋯,zk, respectively, in anticlockwise. We join any vertex up of P with the vertices zp and zp+1 of P´ by edges for p=1,2,⋯,k. The graph of the convex polytope Dk is formed [33], by the dual graph of Ak consisting of the vertices u1,u2,u3,⋯,uk,x1,x2,x3,⋯,xk;y1,y2,y3,⋯,yk; and z1,z2,z3,⋯,zk. It consists of 5-sided and k-sided faces. For compete details, see Figure 1.Figure 1
Graph ofDk.The convex polytopeQk defined in [34] has faces of 3 sides, 4 sides, 5 sides, and n-sides. The vertex set for the graph of the convex polytope Qk is the same as that of the convex polytope Dk, and also, EQk=EDk∪xpxp+1:1≤p≤k.Let us call the verticesup,1≤p≤k, xp,1≤p≤k, yp,1≤p≤k, and zp,1≤p≤k as the inner vertices, the middle vertices, the interior vertices, and the outer vertices, respectively. The cycles induced by up,1≤p≤k, xp,1≤p≤k, and zp,1≤p≤k are the inner cycle, the middle cycle, and the outer cycle respectively, as shown in Figure 2.Figure 2
Graph ofQk.Theorem 1.
For both type of convex polytopesDk and Qk, β′=4 for k≥6, where k is an integer.Proof.
Case I:k is even: let k=2n; n∈Z+, and n≥3. Let F=u1,u2,un+1,un+2. We shall prove that F is a fault-tolerant metric basis for Dk and Qk in the present case. We prove that the metric representations of all vertices of Dk and Qk with respect to F are distinct in at least two coordinates. We call uk+1, xk+1, yk+1, and zk+1 as the vertices of inner cycle, the inner vertices, the outer vertices, and the vertices of outer cycle, respectively.The metric representations of vertices lying on the inner cycle are(1)rup|F=−1+p,−2+p,n+1−p,n+2−p,if3≤p≤n,2n+1−p,2n+2−p,p−1−n,p−2−n,ifn+3≤p≤2n.The metric representations of vertices belonging to inner vertices are(2)rxp|F=1,2,n+1,n,ifn=1,p,−1+p,n+2−p,n+3−p,if2≤p≤n+1,2n+2−p,2n+3−p,p−n,p−1−n,ifn+2≤p≤2n.The metric representations of vertices belonging to outer vertices are(3)ryp|F=2,2,n+1,n+1,ifp=1,p+1,p,n+2−p,n+3−p,if2≤p≤n,n+1,n+1,2,2,ifp=n+1,2n+2−p,2n+3−p,p+1−n,p−n,ifn+2≤p≤2n.The metric representations of vertices lying on the outer cycle are(4)rzp|F=3,3,2+n,2+n,ifp=1,2+p,1+p,3+n−p,4+n−p,if2≤p≤n,n+2,n+2,3,3,ifp=n+1,2n+3−p,2n−p+4,p−n+2,p−n+1,ifn+2≤p≤2n.These representations are distinct in at least two coordinates. So,F is an FTRS. Therefore, for both Dk and Qk, β′≤4. Since for both Dk and Qk, β=3 as proved in [21], so β′>3. Hence, β′=4 when k is even.Case II:k is an odd integer: let k=2n+1 where n∈Z+ and n≥3, and F=u1,u2,un+1,un+2. We shall prove that F is a fault-tolerant metric basis for Dk and Qk in the present case. We prove that the metric representations of all vertices of Dk and Qk with respect to F are distinct in at least two coordinates.
The metric representations of vertices lying on the inner cycle are(5)rup|F=−1+p,−2+p,1+n−p,2+n−p,if3≤p≤n,2n+2−p,2n+3−p,p−n−1,p−n−2,ifn+3≤p≤2n+1.
The metric representations of inner vertices are(6)rxp|F=1,2,n+1,n+1,ifp=1,p,−1+p,2+n−p,3+n−p,if2≤p≤n+1,n+1,n+1,2,1,ifp=n+2,2n−p+3,2n−p+4,p−n,p−n−1,ifn+3≤p≤2n+1.
The metric representations of outer vertices are(7)ryp|F=2,2,n+1,n+2,ifp=1,p+1,p,n−p+2,n−p+3,if2≤p≤n,n+2,n+1,2,2,ifp=n+1,2n−p+3,2n−p+4,p−n+1,p−n,ifn+2≤p≤2n+1.
The metric representations of vertices on the outer cycle are(8)rzp|F=3,3,2+n,n+3,ifp=1,2+p,1+p,n+3−p,n+4−p,if2≤p≤n,n+3,n+2,3,3,ifp=n+1,2n−p+3,2n−p+4,p−n+2,p−n+1,ifn+2≤p≤2n+1.
These representations are distinct in at least two coordinates. So,F is an FTRS. Therefore, for both Dk and Qk, β′≤4. Since for both Dk and Qk, β=3 as proved in [21], so β′>3. Hence, β′=4 when k is odd.


## 2.2. Fault Tolerance in Metric Dimension of Multilevel Wheel

In this part, we focus on the FTMD of multilevel wheelWn,m. An m wheel graph of size n is defined as follows: an m wheel graph of size n can be composed of mCn+K1. It consists of m cycles of size n, where the vertices of the m cycles are all connected to a common hub. Thus, Wn,m has nm+1 vertices, the center, and n rim vertices and has diameter 2. Figure 3 represents the graph of W8,m.Figure 3
Graph ofW8,m.A classical wheel graph is simply a specialized wheel with a single level denoted asWn,1 or simply Wn. Here, we give the graph of W8,1 in Figure 4.Figure 4
A graph ofW8,1 wheel.We do not include the central vertex in the representation of the above graphW8,1. In the above graph, the vertices of the graph G are VG=v1,v2,v3,v4,v5,v6,v7,v8. Now, consider the resolving sets R1 = v2,v4,v6, R2 = v2,v6,v8, R3 = v2,v4,v8, and R4 = v4,v6,v8. For R1 = v2,v4,v6, it is easy to see that rv1/R1 = 1,2,2, rv2/R1 = 0,2,2, rv3/R1 = 1,1,2, rv4/R1 = 2,0,2, rv5/R1 = 2,1,1, rv6/R1 = 2,2,0, rv7/R1 = 2,2,1, and rv8/R1 = 2,2,2. Since the vertices of G have distinct representations with respect to R1, R1 is a resolving set. Since metric dimension of a wheel graph W8 is 3, R1 is a basis for G because it has metric dimension 3. Similarly, R2, R3, and R4 are also basis for G with metric dimension 3. Now, R5 = R1∪R2∪R3∪R4 or R5 = v2,v4,v6,v8.We see thatR5\v is also a resolving set for each v in R5. As βW8,1 of the above example is 3, therefore, β,W8,1=4. Hence, R5 is a fault-tolerant metric basis with β,W8,1=4, so R5 is an FTMS.IfB´ is a resolving set of the graph G, which contains two or more vertices of G, and we suppose that the vertices of B´=vj1,vj2,⋯,vjr, so the j1<j2<⋯<jr. We shall say that the vertices vja, vja+1 for i=1,2,⋯,r−1, and vjr, vj1 are neighboring vertices. Now, the vertices lying between these neighboring vertices are referred to as the gap of B´ and the number of vertices in a gap will be referred to as the size of the gap. If B´ is t, then it has t gapes, and some of which may be empty. For example, the gap between v2andv4 in Figure 4 is 1 because there is only one vertex v3 in between v2 and v4. Now, let B is an FTMS of Wn,m. If we do not include the central vertex, then we make the following two conditions:(1)
Ifn is even, then every gap of B contains exactly one vertex. If a gap contains zero vertex, then B\v does not remain as an FTMS. Similarly, if a gap contains two or more vertices, then again B\v does not remain as an FTMS, which is a contradiction.(2)
Ifn is odd, then every gap of B contains exactly one vertex except for one gap which contains zero vertex. If more than one gap contains zero vertex, then B\v does not remain as an FTMS. Similarly, if a gap contains two or more vertices, then again B\v does not remain as an FTMS, which is a contradiction.Our aim in this section is to compute the FTMD of wheelWn and generalize the wheel graph Wn,r. In [5], it was shown that dimWn=2n+5/2, for every n≥7. Now, suppose that B′ is any fault-tolerant metric basis of Wn. We observe the following results in the form of lemmas and theorems.


### 2.2.1. Lemmas

Lemma 1.
Ifn is even and n≥8, then every gap of B′ (fault-tolerant basis) contains exactly one vertex.Proof.
(i)
Suppose on the contrary, there exists a gap which contains two vertices and at least one of its neighboring gaps contains one vertex. Then,∃vi,vi+1,vi+2,vi+3,vj (where vj is neighboring vertex of vi+3 and contains one vertex), such that vi,vi+3, vj belong to B′. Then, by B′\vi+3, we obtained rvi+2/B′ = rvi+3/B′ = 2,2,2,⋯,2, which is a contradiction.(ii)
Now, again on the contrary, there exists a gap which contains two vertices and its neighboring gaps are empty. Then, there exist verticesvi,vi+1,vi+2,vi+3,vi+4,vi+5,vj (where vj is neighboring vertex of vi+5 and is empty while another neighboring gap of vi is not empty), such that vi,vi+1,vi+4,vi+5,vj belong to B′. Then, by B′\vi, we have rvi/B′ = rvi+2/B′ = 1,2,2,⋯,2, which is a contradiction.(iii)
Now, again on the contrary, there exists a gap which contains two vertices and its neighboring gaps are empty. Then, there exist verticesvi,vi+1,vi+2,vi+3,vi+4,vi+5,vi+6,vi+7. Then, there exists vj, any other vertex of B′, such that vi,vi+1,vi+2,vi+5,vi+6,vi+7,vj belong to B′. Then, by B′\vj, we have rvn−1/B′ = rvn−2/B′ = 2,2,2,⋯,2, which is a contradiction.Lemma 2.
Ifn is odd and n≥7, then every gap of B′ (fault-tolerant basis) contains exactly one vertex except for one gap which is empty.Proof.
Suppose on the contrary, there exists a gap which contains two vertices. Then,∃vi,vi+1,vi+2,vi+3,vj (where vj is neighboring vertex of vi+3), such that vi,vi+3, vj belong to B′. Then, by B′\vj, we have rvi+2/B′ = rvi+4/B′, which is a contradiction.Lemma 3.
The resolving set ofCn of the type B′ = v1,v3,v5,……vn−1 or B′ = v2,v4,v6,……vn is fault-tolerant metric basis.Proof.
We see from Lemmas1 and 2 that B′ can be an FTMS because for each v in B′, the set B′\v is a resolving set. Now, we see that the set B′\v1,v3 or B′\v2,v4 is not a resolving set, which is a contradiction. Hence, B′ is a fault-tolerant metric basis.Lemma 4.
IfC1 and C2 denote the vertices of circle 1 and circle 2, respectively, then fault-tolerant metric basis for C1 and C2 is the same.Proof.
LetC1 and C2 denote the set of vertices of circle 1 and circle 2, respectively. Let vi∈C1 and wi∈C2. Now, dvi,wi=dwi,vi=2. Also, there does not exist any vi belongs to C1 such that by B′\vi, we get rvj/B′ = rvr/B′ = (2, 2, 2, ⋯, 2). Similarly, there does not exist any wi belongs to C2 such that by B′\vi, we get rwj/B′ = rwr/B′ = (2, 2, 2, ⋯, 2). In the same way, we can show that all levels have the same FTMS.
Now, we move towards the main results of this section.Theorem 2.
Ifn≥7 and m≥1, then we have β,Wn,m=mn/2.Proof.
(whenm=1).
We divide the proof into the following two cases based on parity ofn.(i)
Case I:. when n is even: if n is even, then we can write n=2k+4, where k≥2 and β,Wn,1=⌊n/2⌋=k+2. Then, B=V2i,1≤i≤n/2 is an FTMS as it satisfies conditions 1 and 2.(ii)
Case II: when n is odd: when n is odd, then we may write n=2k+3, where k≥2 and β,Wn,1=n/2=k+2. B=V1,V2i,1≤i≤n−1/2. It is an FTMS as it satisfies conditions 1 and 2. It follows from the above discussion that β,Wn,1=n/2.
Next, we show thatβ,Wn,1=n/2 is the cardinality of FTMS. From Case 1 and Case 2, one can note that B can be an FTMS because for each v in B, the set B\v is a resolving set. Now, we show that B is an FTMS. Suppose that B is not an FTMS, then there exists vertex v in B such that C = B\v is an FTMS. Since C is an FTMS as each v in C, C\v should be a resolving set. However, C\v is not a resolving set which is a contradiction. Hence, B is an FTMS.Proof.
(whenm=2).
(i)
Case I: when n is even: when n is even, then we may write n=2k+4, where k≥2 and β,Wn,2=2n/2 = 2 (k + 2). Then, B=v2i,w2i,1≤i≤n/2 is an FTMS as it satisfies conditions 1 and 2.(ii)
Case II: when n is odd: then, we may write n=2k+3, where k≥2 and β,Wn,2=2n/2 = 2 (k + 2). Then, B=v1,v2i,w1,w2i,1≤i≤n−1/2 is an FTMS as it satisfies both conditions 1 and 2. It follows from the above discussion that β,Wn,2=2n/2.
Next, we show thatβ,Wn,2=2n/2 is the cardinality of the FTMS. We see from Case 1 and Case 2 that B can be an FTMS because for each v in B, the set B\v is a resolving set. We show that B is an FTMS. Suppose on the contrary that B is not an FTMS, then there exists a v in B such that C = B\v is an FTMS. Now, C is an FTMS. Therefore, for each v in C, C\v should be a resolving set. However, C\v is not a resolving set which is a contradiction. Hence, B is an FTMS.Proof.
(whenm≥3). We shall prove this case by mathematical induction.
For level 1, we havem=1 and then β′Wn,1=n/2. For level 2, i.e., m=2, we have β′Wn,2=2n/2. Now, we suppose that the assertion is true for level k, i.e.,(9)β′Wn,k=kn/2·1.
We shall show that it is true form=k+1. We have β′Wn,k+1=β′Wn,k+β′Wn,1.
Then,(10)β′Wn,k+1=kn2+n2,β′Wn,k+1=k+1n2.
Hence, the given statement is true for all positive integersm≥3.


## 2.2.1. Lemmas

Lemma 1.
Ifn is even and n≥8, then every gap of B′ (fault-tolerant basis) contains exactly one vertex.Proof.
(i)
Suppose on the contrary, there exists a gap which contains two vertices and at least one of its neighboring gaps contains one vertex. Then,∃vi,vi+1,vi+2,vi+3,vj (where vj is neighboring vertex of vi+3 and contains one vertex), such that vi,vi+3, vj belong to B′. Then, by B′\vi+3, we obtained rvi+2/B′ = rvi+3/B′ = 2,2,2,⋯,2, which is a contradiction.(ii)
Now, again on the contrary, there exists a gap which contains two vertices and its neighboring gaps are empty. Then, there exist verticesvi,vi+1,vi+2,vi+3,vi+4,vi+5,vj (where vj is neighboring vertex of vi+5 and is empty while another neighboring gap of vi is not empty), such that vi,vi+1,vi+4,vi+5,vj belong to B′. Then, by B′\vi, we have rvi/B′ = rvi+2/B′ = 1,2,2,⋯,2, which is a contradiction.(iii)
Now, again on the contrary, there exists a gap which contains two vertices and its neighboring gaps are empty. Then, there exist verticesvi,vi+1,vi+2,vi+3,vi+4,vi+5,vi+6,vi+7. Then, there exists vj, any other vertex of B′, such that vi,vi+1,vi+2,vi+5,vi+6,vi+7,vj belong to B′. Then, by B′\vj, we have rvn−1/B′ = rvn−2/B′ = 2,2,2,⋯,2, which is a contradiction.Lemma 2.
Ifn is odd and n≥7, then every gap of B′ (fault-tolerant basis) contains exactly one vertex except for one gap which is empty.Proof.
Suppose on the contrary, there exists a gap which contains two vertices. Then,∃vi,vi+1,vi+2,vi+3,vj (where vj is neighboring vertex of vi+3), such that vi,vi+3, vj belong to B′. Then, by B′\vj, we have rvi+2/B′ = rvi+4/B′, which is a contradiction.Lemma 3.
The resolving set ofCn of the type B′ = v1,v3,v5,……vn−1 or B′ = v2,v4,v6,……vn is fault-tolerant metric basis.Proof.
We see from Lemmas1 and 2 that B′ can be an FTMS because for each v in B′, the set B′\v is a resolving set. Now, we see that the set B′\v1,v3 or B′\v2,v4 is not a resolving set, which is a contradiction. Hence, B′ is a fault-tolerant metric basis.Lemma 4.
IfC1 and C2 denote the vertices of circle 1 and circle 2, respectively, then fault-tolerant metric basis for C1 and C2 is the same.Proof.
LetC1 and C2 denote the set of vertices of circle 1 and circle 2, respectively. Let vi∈C1 and wi∈C2. Now, dvi,wi=dwi,vi=2. Also, there does not exist any vi belongs to C1 such that by B′\vi, we get rvj/B′ = rvr/B′ = (2, 2, 2, ⋯, 2). Similarly, there does not exist any wi belongs to C2 such that by B′\vi, we get rwj/B′ = rwr/B′ = (2, 2, 2, ⋯, 2). In the same way, we can show that all levels have the same FTMS.
Now, we move towards the main results of this section.Theorem 2.
Ifn≥7 and m≥1, then we have β,Wn,m=mn/2.Proof.
(whenm=1).
We divide the proof into the following two cases based on parity ofn.(i)
Case I:. when n is even: if n is even, then we can write n=2k+4, where k≥2 and β,Wn,1=⌊n/2⌋=k+2. Then, B=V2i,1≤i≤n/2 is an FTMS as it satisfies conditions 1 and 2.(ii)
Case II: when n is odd: when n is odd, then we may write n=2k+3, where k≥2 and β,Wn,1=n/2=k+2. B=V1,V2i,1≤i≤n−1/2. It is an FTMS as it satisfies conditions 1 and 2. It follows from the above discussion that β,Wn,1=n/2.
Next, we show thatβ,Wn,1=n/2 is the cardinality of FTMS. From Case 1 and Case 2, one can note that B can be an FTMS because for each v in B, the set B\v is a resolving set. Now, we show that B is an FTMS. Suppose that B is not an FTMS, then there exists vertex v in B such that C = B\v is an FTMS. Since C is an FTMS as each v in C, C\v should be a resolving set. However, C\v is not a resolving set which is a contradiction. Hence, B is an FTMS.Proof.
(whenm=2).
(i)
Case I: when n is even: when n is even, then we may write n=2k+4, where k≥2 and β,Wn,2=2n/2 = 2 (k + 2). Then, B=v2i,w2i,1≤i≤n/2 is an FTMS as it satisfies conditions 1 and 2.(ii)
Case II: when n is odd: then, we may write n=2k+3, where k≥2 and β,Wn,2=2n/2 = 2 (k + 2). Then, B=v1,v2i,w1,w2i,1≤i≤n−1/2 is an FTMS as it satisfies both conditions 1 and 2. It follows from the above discussion that β,Wn,2=2n/2.
Next, we show thatβ,Wn,2=2n/2 is the cardinality of the FTMS. We see from Case 1 and Case 2 that B can be an FTMS because for each v in B, the set B\v is a resolving set. We show that B is an FTMS. Suppose on the contrary that B is not an FTMS, then there exists a v in B such that C = B\v is an FTMS. Now, C is an FTMS. Therefore, for each v in C, C\v should be a resolving set. However, C\v is not a resolving set which is a contradiction. Hence, B is an FTMS.Proof.
(whenm≥3). We shall prove this case by mathematical induction.
For level 1, we havem=1 and then β′Wn,1=n/2. For level 2, i.e., m=2, we have β′Wn,2=2n/2. Now, we suppose that the assertion is true for level k, i.e.,(9)β′Wn,k=kn/2·1.
We shall show that it is true form=k+1. We have β′Wn,k+1=β′Wn,k+β′Wn,1.
Then,(10)β′Wn,k+1=kn2+n2,β′Wn,k+1=k+1n2.
Hence, the given statement is true for all positive integersm≥3.


## 3. Examples

### 3.1. Example 1

Now, we give some examples to compute the FTMD of theEW11,1 wheel graph.We see from Theorem3 that the FTMD of W11,1 is equal to 6 and the fault-tolerant metric basis for EW11,1 is B=v1,v2,v4,v6,v8,v10. We see that B=v1,v4,v6,v10 is a metric basis for W11,1 with cardinality 4. In order to find fault-tolerant metric basis with cardinality 5, we need other four metric bases having cardinality 4 other than B=v1,v4,v6,v10. However, W11,1 has only one metric basis with cardinality 4. It means that there is no fault-tolerant metric basis with cardinality 5. So, we need to add two vertices to find fault-tolerant metric basis. Hence, B=v1,v2,v4,v6,v8,v10 is a fault-tolerant metric basis with cardinality 6, and it also satisfies Lemma 1.


### 3.2. Example 2

We also give another example to compute the FTMD of theEW11,2 wheel graph and verify.We see from Theorem4 that the FTMD of EW11,2 is equal to 12 and the fault-tolerant metric basis for EW11,2 is B=v1,v2,v4,v6,v8,v10,w1,w2,w4,w6,w8,w10. The FTMD for level 2 m=2 will be the same as that of level 1 m=1 because level 2 contains the same number of vertices as that of level 1. Hence, B=v1,v2,v4,v6,v8,v10,w1,w2,w4,w6,w8,w10 is a fault-tolerant metric basis with cardinality 12, and it also satisfies Lemmas 1 and 2.


## 3.1. Example 1

Now, we give some examples to compute the FTMD of theEW11,1 wheel graph.We see from Theorem3 that the FTMD of W11,1 is equal to 6 and the fault-tolerant metric basis for EW11,1 is B=v1,v2,v4,v6,v8,v10. We see that B=v1,v4,v6,v10 is a metric basis for W11,1 with cardinality 4. In order to find fault-tolerant metric basis with cardinality 5, we need other four metric bases having cardinality 4 other than B=v1,v4,v6,v10. However, W11,1 has only one metric basis with cardinality 4. It means that there is no fault-tolerant metric basis with cardinality 5. So, we need to add two vertices to find fault-tolerant metric basis. Hence, B=v1,v2,v4,v6,v8,v10 is a fault-tolerant metric basis with cardinality 6, and it also satisfies Lemma 1.


## 3.2. Example 2

We also give another example to compute the FTMD of theEW11,2 wheel graph and verify.We see from Theorem4 that the FTMD of EW11,2 is equal to 12 and the fault-tolerant metric basis for EW11,2 is B=v1,v2,v4,v6,v8,v10,w1,w2,w4,w6,w8,w10. The FTMD for level 2 m=2 will be the same as that of level 1 m=1 because level 2 contains the same number of vertices as that of level 1. Hence, B=v1,v2,v4,v6,v8,v10,w1,w2,w4,w6,w8,w10 is a fault-tolerant metric basis with cardinality 12, and it also satisfies Lemmas 1 and 2.


## 4. Conclusions and Open Problem

In this article, we computed the FTMD of graphs of two convex polytopes denoted byDn and Qn. We conclude that all these graphs have constant FTMD.Theorem 3.
The fault-tolerant metric dimension of convex polytopesDn is 4 for n≥4.Theorem 4.
The fault-tolerant metric dimension of convex polytopesQn is 4 for n≥6.We pose a natural open problem: Does there exist the graph of a convex polytope which has nonconstant FTMD? We also computed the FTMD of generalized wheel and arrive in the following theorem.Theorem 5.
Ifn≥7 and m≥1, then we have β′Wn,m=mn/2.In Table1, we presented the comparison between the metric dimension and fault-tolerant metric dimension for generalized wheel graphs.Table 1
Comparison table for generalized wheel graphs.
nβ′Wn,1β′Wn,2β′Wn,mβ′Wn,1β′Wn,2β′Wn,m7373m + 2484m8374m − 1484m9494m5105m˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙n⌊2n+25⌋⌊2n+25⌋+⌈2n+45⌉⌊2n+25⌋+m−1⌊2n+45⌋⌈n2⌉2⌈n2⌉m⌈n2⌉



---

*Source: 1216542-2020-11-04.xml*