A set of vertices S is a resolving set of a graph G, if for every pair of vertices x and y in G, there exists a vertex s in S such that x and y differ in distance to s. A smallest resolving set of G is called a metric basis. The metric dimension \(\textrm{dim}(G)\) is the cardinality of a metric basis of G. The notion of a metric basis is applied to the problem of placing sensors in a network, where the problem of sensor faults can arise. The fault-tolerant metric dimension \(\textrm{ftdim}(G)\) is the cardinality of a smallest resolving set S such that \(S\setminus \{s\}\) remains a resolving set of G for every \(s\in S\) . A natural question is how much more sensors need to be used to achieve a fault-tolerant metric basis. It is known in literature that there exists an upper bound on \(\textrm{ftdim}(G)\) which is exponential in terms of \(\textrm{dim}(G),\) i.e. \(\textrm{ftdim}(G)\le \textrm{dim}(G)(1+2\cdot 5^{\textrm{dim}(G)-1}).\) In this paper, we construct graphs G with \(\textrm{ftdim}(G)=\textrm{dim}(G)+2^{\textrm{dim}(G)-1}\) for any value of \(\textrm{dim}(G)\) , so the exponential upper bound is necessary. We also extend these results to the k-metric dimension which is a generalization of the fault-tolerant metric dimension. First, we establish a similar exponential upper bound on \(\textrm{dim}_{k+1}(G)\) in terms of \(\textrm{dim}_{k}(G),\) and then we show that there exists a graph for which \(\textrm{dim}_{k+1}(G)\) is indeed exponential. For a possible further work, we leave the gap between the bounds to be reduced.
