# Fault-Tolerant Resolvability and Extremal Structures of Graphs
## 2 Preliminaries  
This section defines the terminologies and explains the undefined terms from the previous section. We also provide an overview of basic results in the literature which are used in subsequent sections. Notations and graph-theoretic concepts were taken from [PERSON] and [PERSON] [PERSON] and [PERSON] (2007). A graph is an ordered pair \(\Gamma=(V,E)\), where \(V\) is considered to be the vertex set and \(E\) is called the edge set. \(\Gamma\) is called finite if \(V\) is finite; it is said to be simple if it does not contain any loop and parallel edges; it is called undirected if its edges do not possess direction; and it is called connected if any two vertices in it are connected by a path. The length of the shortest path between two given vertices is called the distance between them. For \(u,v\in V\), the distance between \(u\) and \(v\) is usually denoted as \(d_{u,v}\). For two arbitrary vertices \(x\) and \(y\), a vertex \(u\) is said to resolve the pair \(x,\ y\) if it satisfies \(d_{u,x}\
eq d_{u,y}\). If this resolvability condition is satisfied by a number of vertices composing a subset \(R\subseteq V\), i.e., any pair of vertices in the graph is resolved by at least one vertex in \(R\), then \(L\) is said to be a resolving set. The idea behind this definition goes back to [PERSON] and [PERSON] [PERSON] and [PERSON] (1994), who showed that this concept naturally arises from communication networks. The minimum cardinality of a resolving set in a given graph is said to be the metric dimension. It is usually denoted by \(\beta(G)\). A resolving set in which the number of elements is \(\beta\) is called the metric basis. For an ordered subset \(R=(x_{1},x_{2},\ldots,x_{r})\), the \(R\)-coordinate/code/representation of vertex \(u\) in \(V\) is \(C_{R}(u)=(d_{u,x_{1}},d_{u,x_{2}},\ldots,d_{u,x_{r}})\). In these terms, \(L\) is said to be a resolving set of \(\Gamma\) if any two vertices in \(\Gamma\) have distinct codes or distance vectors. [PERSON] et al. [PERSON] et al. (2016) determined all the connected graphs with metric dimension 1. Let \(P_{v}\) be the \(v\)-vertex path graph. Theorem 1: ([PERSON] et al., 2016) _A connected graph has metric dimension 1 if and only if it is the path graph._  
They also showed that a graph having metric dimension 2 cannot possess \(K_{3,3}\) and \(K_{5}\) as its subgraphs. Let \(K_{v}\) be the complete graph on \(v\) vertices. They also classified the connected graphs possessing metric dimension \(v-1\). Theorem 2: ([PERSON] et al., 2016) _A connected \(v\)-vertex graph has metric dimension \(v-1\) if and only if it is the complete graph._  
Let \(\Gamma\cup\Omega\) denote the disjoint union of two graphs \(\Gamma\) and \(\Omega\). The join of two graphs \(\Gamma\) and \(\Omega\), symbolized as \(\Gamma+\Omega\), is obtained by joining any vertex of \(\Gamma\) to all the vertices of \(\Omega\) and vice versa. Graphs having \(v\) vertices sharing the metric dimension \(v-2\) are classified in the following result. Theorem 3: ([PERSON] et al., 2016)_A connected \(v\)-vertex graph \(\Gamma\) with \(v\geq 4\) shares the metric dimension \(v-2\) if and only if \(\Gamma\in\{K_{s}+\overline{K_{t}}\ (s\geq 1,t\geq 2),K_{s,t}\ (s,t\geq 1),K_{s}+(K_{1} \cup K_{t})\ (s,t\geq 1)\}\)._  
A fault-tolerant resolving set is a resolving set in which the removal of an arbitrary vertex maintains the resolvability. The idea of a fault-tolerant resolving set (also known as resilient) has been widely investigated in networked systems; see, for example, [PERSON] (2008); [PERSON] (2009). The fault-tolerant metric dimension and fault-tolerant metric basis are defined similarly as metric dimension. We denote the fault-tolerant metric dimension of graph \(\Gamma\) by \(\beta^{\prime}(\Gamma)\). A family of graphs on \(v\) vertices is said to possess a constant (resp. bounded) resolvability/fault-tolerant resolvability structure if the metric dimension/fault-tolerant metric dimension does not depend on the parameter \(v\) (resp. is a function of \(v\)).