# Fault-Tolerant Resolvability and Extremal Structures of Graphs
## 2 Preliminaries
### Extended Petersen Graphs
\begin{array}{ll}(k+1,k+1),& 1\leq k\leq\ell;\\ (2\ell-k+2,2\ell-k+2),&\ell+1\leq k\leq 2\ell.\end{array} \right.\]  
Now, the representations of the vertices in the inner cycle are  
\[C_{R\setminus\{y_{z_{2\ell-1}\}}}(y_{2k})=\left\{ \begin{array}{ll}(k+2,k-1),&2\leq k\leq\ell-1;\\ (k+1,k-1),&k=\ell;\\ (k-1,k-1),&k=\ell+1;\\ (k-3,k-1),&k=\ell+2;\\ (2\ell-k+1,2\ell-k+4),&\ell+3\leq k\leq 2\ell.\end{array} \right.\]  
and  
\[C_{R\setminus\{z_{2\ell-1}\}}(y_{2k+1})=\left\{ \begin{array}{ll}(k,k+2),&1 \leq k\leq\ell-1;\\ (k,k+1),&k=\ell;\\ (k,k-1),&k=\ell+1;\\ (2\ell-k+3,2\ell-k+1),&\ell+2\leq k\leq 2\ell.\end{array} \right.\]  
From the above discussion, it is clear that \(R\setminus\{z_{2\ell-1}\}\) distinguishes all but the following vertices. (i) \(z_{3+k}\) and \(z_{n-k}\) for \(i=0,2,\ldots,2\ell-6\). (ii) \(z_{2\ell-1}\) and \(z_{2\ell+5}\) and \(y_{2\ell+2}\). (iii) \(z_{2\ell+1}\), \(z_{2\ell+2}\), and \(z_{2\ell+3}\). (iv) \(y_{2\ell-1}\) and \(y_{2\ell+4}\). (v) \(y_{2\ell}\) and \(y_{2\ell+5}\). (vi) \(z_{2\ell}\) and \(y_{2\ell+3}\). (vii) \(y_{2\ell+1}\) and \(z_{2\ell+4}\). It is easy to see that vertices with the same representation in the outer cycle are at different distances from \(z_{2\ell-1}.d(z_{2\ell-1},z_{2\ell+5})=5\) and \(d(z_{2\ell-1},y_{2\ell+2})=3\), \(d(z_{2\ell-1},y_{2\ell-1})=1\) and \(d(z_{2\ell-1},y_{2\ell+4})=4\), \(d(z_{2\ell-1},y_{2\ell+2})=2\) and \(d(z_{2\ell-1},y_{2\ell+5})=4\), \(d(z_{2\ell-1},z_{2\ell})=1\) and \(d(z_{2\ell-1},y_{2\ell+3})=3\), \(d(z_{2\ell-1},y_{2\ell+1})=2\) and \(d(z_{2\ell-1},z_{2\ell+4})=5\). The above discussion shows that \(R\) is a resolving set for \(V(\Gamma)\) when \(n\equiv 1(\mod 4)\). Hence, \(\beta(\Gamma))\leq 3\) for \(n\equiv 1(\mod 4)\). **Claim 2:**\(\Gamma\) has a fault-tolerant resolving set of cardinality \(12\) when \(n\geq 11\). We can write \(n=4\ell+1\), \(\ell\geq 3\) and \(\ell\in\mathbb{Z}^{+}\). Note that, in this case, \(R=\{y_{1},y_{2},z_{2\ell-1}\}\) is a resolving set of \(\Gamma\). We prove here that \(\Gamma\) has a fault-tolerant resolving set of cardinality \(12\). From Figure 3, it can be observed that \(N[y_{1}]=\{y_{1},y_{n-1},y_{n},z_{1}\}\), \(N[y_{2}]=\{y_{2},y_{4},y_{n},z_{2}\}\) and \(\{z_{2\ell-2},z_{2\ell-1},z_{2\ell},y_{2\ell-1}\}\). Moreover, we find that \(\lambda(N_{\Gamma}(y_{1}))=\lambda(N_{\Gamma}(y_{2}))=\lambda(N_{\Gamma}(z_{2\ell -1}))=\emptyset\). Thus, by using Lemma 3, we find that \(R^{\prime}=\{y_{1},y_{2},y_{3},y_{4},y_{2\ell-1},y_{n-1},y_{n},z_{1},z_{2},z_{ 2\ell-2},z_{2\ell-1},z_{2\ell}\}\) is a fault-tolerant resolving set of \(\Gamma\). Thus, there exists a fault-tolerant resolving set of \(\Gamma\) with cardinality \(12\). **Subcase 2.2:** When \(n\equiv 3(\mod 4)\). **Claim 1:** Resolving set \(R\) of order \(3\) in \(\Gamma\) exists. We can write \(n=4\ell+3\), \(1\leq\ell\in\mathbb{Z}^{+}\). It is not difficult to see that \(U=\{y_{1},y_{2},z_{3}\}\) resolves \(V(P(7))\). For \(n\equiv 3(\mod 4)\) and \(n\geq 11\), we show that \(R=\{y_{1},y_{2},z_{2\ell+1}\}\) resolves \(V(\Gamma=P(n))\). Representations of the vertices in the outer cycle are \(C_{R\setminus\{z_{2\ell+1}\}}(z_{1})=(1,2)\), \(C_{R\setminus\{z_{2\ell+1}\}}(z_{2})=(2,1)\),  
\[C_{R\setminus\{z_{2\ell+1}\}}(z_{2k})=\left\{ \begin{array}{ll}(k+1,k),&2\leq k \leq\ell+1;\\ (2\ell-k+3,2\ell-k+4),&\ell+2\leq k\leq 2\ell+1.\end{array} \right.\]  
and  
\[C_{R\setminus\{z_{2\ell+1}\}}(z_{2k+1})=\left\{ \begin{array}{ll}(k+1,k+1),&1 \leq k\leq\ell+1;\\ (2\ell-k+3,2\ell-k+3),&\ell+2\leq k\leq 2\ell+1.\end{array} \right.\]  
Now, in the inner cycle,  
\[C_{R\setminus\{z_{2\ell+1}\}}(y_{2k})=\left\{ \begin{array}{ll}(k+2,k-1),&2 \leq k\leq\ell;\\ (k,k-1),&k=\ell+1;\\ (k-2,k-1),&k=\ell+2;\\ (2\ell-k+2,2\ell-k+5),&\ell+3\leq k\leq 2\ell+1.\end{array} \right.\]  
and  
\[C_{R\setminus\{z_{2\ell+1}\}}(z_{2k+1})=\left\{ \begin{array}{ll}(k,k+2),&1 \leq k\leq\ell;\\ (k,k),&k=\ell+1;\\ (2\ell-k+4,2\ell-k+2),&\ell+2\leq k\leq 2\ell+1.\end{array}