# Fault-Tolerant Resolvability and Extremal Structures of Graphs
## 2 Preliminaries
### Extended Petersen Graphs  
The extended Petersen graph \(P(n)\), \(n\geq 3\), has a vertex set  
\[V=\{z_{1},z_{2},\ldots z_{n},y_{1},y_{2},\ldots y_{n}\}\]  
and an edge set  
\[E=\{z_{i}z_{i+1},z_{i}y_{i},y_{i}y_{i+2}|\text{with indices taken as modulo $n$}\}.\]  
The extended Petersen graph \(P(n)\) is a special case of the generalized Petersen graphs which were first studied by [PERSON] [33]. We studied the problem of the fault-tolerant metric dimension of the extended Petersen graph. The set \(\{z_{1},z_{2},\ldots,z_{n}\}\) prompts a cycle in \(P(n)\), with \(z_{k}z_{k+1}\) (\(1\leq k\leq n\)) and \(y_{k}y_{k+2}\) (\(1\leq k\leq n\)), with indices taken modulo \(n\), as edges. For even \(n\), \(\{y_{1},y_{2},\ldots,y_{n}\}\) induces two cycles, again with edges \(y_{k}y_{k+2}\) (\(1\leq k\leq n\)), with indices taken modulo \(n\). For example, \(P(5)\) is the standard Petersen graph. For the sake of simplicity, we denote the cycle induced by \(\{z_{1},z_{2},\ldots,z_{n}\}\) as the outer cycle and the cycle induced by \(\{y_{1},y_{2},\ldots,y_{n}\}\) as the inner cycle or cycles. The following result was shown by [PERSON] et al. [34]. Proposition 1: _[_34_]_ _Let \(\Gamma\) be the extended Petersen graph \(P(n)\) with \(n\geq 5\); then, \(\beta(\Gamma)=3\)._  
They also showed the following:  
Proposition 2: _[_34_]_ \(P(n)\), the extended Petersen graph, can be classified as a family of graphs with a constant metric dimension._  
In this section, we present our main results. We derive the upper as well as lower bounds on the fault-tolerant metric dimension of the extended Petersen graph \(P(n)\). Note that Claim 1 in the following result was essentially shown in Proposition 1. Theorem 4.1: _Let \(\Gamma\) be the extended Petersen graph \(P(n)\); then,_  
\[4\leq\beta^{\prime}(\Gamma)\leq\left\{ \begin{array}{ll}10,&if\ n\equiv 0( \mod 2)\text{ with }n\geq 8;\\ 12,&if\ n\equiv 1(\mod 2)\text{ with }n\geq 11.\end{array} \right.\]  
Proof: Let \(\Gamma\) be the extended Petersen graph \(P(n)\), with \(n\geq 4\). **Case 1:** When \(n\equiv 0(\mod 2)\) with \(n\geq 8\). **Claim 1:** Resolving set \(R\) of order 3 exists in \(\Gamma\). Based on the location of basis elements in \(\Gamma\), we further divide this case into two subcases. **Subcase 1.1:** When \(n\equiv 0(\mod 4)\). It can be written as \(n=4\ell\), \(2\leq\ell\in\mathbb{Z}^{+}\). We prove that \(R=\{y_{1},y_{2},y_{3}\}\) resolves \(V(\Gamma)\). In order to show that \(R\) resolves vertices of \(V(\Gamma)\), we first represent the vertices in \(\Gamma\) with respect to \(R\setminus\{y_{3}\}\)Indeed, the vertices \(y_{1}\) and \(y_{2}\) distinguish the inner cycle vertices and a few of the outer cycle vertices. The vertices in the outer cycle are represented by \(C_{R\setminus\{y_{3}\}}(z_{1})=(1,2)\), \(C_{R\setminus\{y_{3}\}}(z_{2})=(2,1)\),  
\[C_{R\setminus\{y_{3}\}}(z_{2k})=\left\{ \begin{array}{ll}(k+1,k),&2\leq k\leq \ell;\\ (2\ell-k+2,2\ell-k+2),&\ell+1\leq k\leq 2\ell.\end{array} \right.\]  
\[C_{R\setminus\{y_{3}\}}(z_{2k+1})=\left\{ \begin{array}{ll}(k+1,k+1),&1\leq k \leq\ell;\\ (2\ell-k+1,2\ell-k+2),&\ell+1\leq k\leq 2\ell-1.\end{array} \right.\]  
In the inner cycle,  
\[C_{R\setminus\{y_{3}\}}(y_{2k})=\left\{ \begin{array}{ll}(k+2,k-1),&2\leq k \leq\ell;\\ (2\ell-k+3,2\ell-k+1),&\ell+1\leq k\leq 2\ell.\end{array} \right.\]  
and  
\[C_{R\setminus\{z_{3}\}}(y_{2k+1})=\left\{ \begin{array}{ll}(k,k+2),&1\leq k \leq\ell;\\ (2\ell-k,2\ell-k+3),&\ell+1\leq k\leq 2\ell-1.\end{array} \right.\]  
From the above discussion, it is clear that there are no two vertices with the same representation in the inner cycle. However, in the outer cycle, \(C_{R\setminus\{y_{3}\}}(z_{3+k})=C_{R\setminus\{y_{3}\}}(z_{n-k})\) for \(k=0,2,\ldots,2\ell-2\). Vertex \(y_{3}\) distinguishes these pairs with the same representation as \(d(y_{3},z_{3+k})=\lfloor\frac{3+k}{2}\rfloor\
eq d(y_{3},z_{n-k})=\lfloor\frac {3+k}{2}\rfloor+2\) for \(k=0,2,\ldots,2\ell-4\) and \(d(y_{3},z_{2\ell+2})=d(y_{3},z_{2\ell+1})+1\).