# Fault-Tolerant Resolvability and Extremal Structures of Graphs
## 2 Preliminaries
### Some Characterizations  
In this subsection, we prove some characterization results on extreme values of the fault-tolerant metric dimension of graphs. These results are the fault-tolerant metric dimension analogs of Theorems 1-3, where similar results on the metric dimension of graphs are obtained. Note that from the interpretation of the fault-tolerant metric dimension of a graph \(\Gamma\) with \(n\) vertices, we have \(2\leq\beta^{\prime}(\Gamma)\leq n\). In the following result, graphs with fault-tolerant metric dimension 2 are characterized. A graph has \(\beta^{\prime}(\Gamma)=2\) if and only if it is the path graph. Proof. : First, we assume that \(\Gamma\cong P_{n}\). By Theorem 1, we obtain \(\beta(\Gamma)=1\). By the definition of the fault-tolerant metric dimension, it is noted that  
\[\beta^{\prime}(\Gamma)\geq\beta(\Gamma)+1. \tag{1}\]  
By inserting \(\beta(\Gamma)=1\) in Equation (1), we get \(\beta^{\prime}(\Gamma)\geq 2\). Let \(R^{\prime}=\{a,b\}\subseteq V(\Gamma)\), where \(a\) and \(b\) are the vertices with degree one in \(\Gamma\). Clearly, \(R^{\prime}\) is a resolving set in \(\Gamma\). Note that both \(R^{\prime}\setminus\{a\}\) and \(R^{\prime}\setminus\{b\}\) are also resolving sets in \(\Gamma\), because any vertex of degree one resolves the path graph. This implies that \(R^{\prime}\) is a fault-tolerant resolving set of \(\Gamma\), and thus, \(\beta^{\prime}(\Gamma)\leq 2\). By combining two inequalities, we obtain \(\beta^{\prime}(\Gamma=P_{n})=2\). Conversely, suppose that \(\Gamma\) is a graph with fault-tolerant metric dimension 2. Since both \(\beta(\Gamma)\) and \(\beta^{\prime}(\Gamma)\) are positive integers, by Equation (1), we get \(\beta(\Gamma)<\beta^{\prime}(\Gamma)\). By implying \(\beta^{\prime}(\Gamma)=2\), we obtain \(\beta(\Gamma)<2\), which indicates that \(\beta(\Gamma)=1\). By Theorem 1, we find that the only graphs with metric dimension 1 are the path graphs. This implies that \(\Gamma\cong P_{n}\). In the next theorem, we characterize the equality in \(\beta^{\prime}(\Gamma)\leq n\), where \(\Gamma\) is an \(n\)-ordered graph. An \(n\)-vertex connected graph has \(\beta^{\prime}(\Gamma)=n\) if and only if it is the complete graph \(K_{n}\). Proof. : Let \(\Gamma\) be an \(n\)-ordered complete graph. Then, by Theorem 2, we have \(\beta(\Gamma)=n-1\). By putting this in Equation (1), we get \(\beta^{\prime}(\Gamma)\geq n\). Let \(R^{\prime}=V(\Gamma)\); for some \(c\in V(\Gamma)\), the set \(R^{\prime}\setminus\{c\}\) is a resolving set, because any collection of \(n-1\) vertices of \(\Gamma\) resolve \(\Gamma\) completely. Thus, \(R^{\prime}\) is a fault-tolerant resolving set of \(\Gamma\), and thus, \(\beta^{\prime}(\Gamma)\leq n\). By combining these two cases, we obtain \(\beta^{\prime}(\Gamma)=n\). Conversely, suppose that \(\Gamma\) is a graph with fault-tolerant metric dimension \(n\). From Equation (1), we have \(\beta(\Gamma)<\beta^{\prime}(\Gamma)\), which shows that \(\beta(\Gamma)\leq n-1\). In Theorem 2, it is shown that equality holds in \(\beta(\Gamma)\leq n-1\) if and only if \(\Gamma=K_{n}\). This shows that equality holds in \(\beta(\Gamma)\leq\beta^{\prime}(\Gamma)-1=n-1\). This implies that \(\Gamma\) is a complete graph on \(n\) vertices. In the next theorem, graphs with fault-tolerant metric dimension \(n-1\) are characterized. Let \(\Gamma\) be a graph with order \(n\geq 4\). Then, \(\beta^{\prime}(\Gamma)=n-1\) if and only if \(\Gamma=K_{s,t}\)\((s,t\geq 1)\), \(\Gamma=K_{s}+\overline{K_{t}}\)\((s\geq 1,t\geq 2)\) and \(\Gamma=K_{s}+(K_{1}\cup K_{t})\)\((s,t\geq 1)\). Proof. : Let \(\Gamma_{1}=K_{s,t}\)\((s,t\geq 1)\), \(\Gamma_{2}=K_{s}+\overline{K_{t}}\)\((s\geq 1,t\geq 2)\), and \(\Gamma_{3}=K_{s}+(K_{1}\cup K_{t})\)\((s,t\geq 1)\). Assume that \(\Gamma\) belongs to one of the three infinite families \(\Gamma_{i}\), \(i=1,2,3\). Then, by Theorem 3, \(\beta(\Gamma)=n-2\). By using this in Inequality (1), we get \(\beta^{\prime}(\Gamma)\geq n-1\).