Fault tolerance of metric basis can be expensiveKnor, Martin (Avtor) Sedlar, Jelena (Avtor) Škrekovski, Riste (Avtor) metric dimensionfault-tolerant metric dimensionk-metric dimensionA 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 $\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 ${\rm 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 ${\rm ftdim}(G)$ which is exponential in terms of $\dim(G)$; i.e. ${\rm ftdim}(G) \le \dim(G)(1+2 \cdot 5^{\dim(G)-1})$. In this paper, we construct graphs $G$ with ${\rm ftdim}(G) = \dim(G)+2^{\dim(G)-1}$ for any value of $\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 $\dim_{k+1}(G)$ in terms of $\dim_k(G)$; and then we show that there exists a graph for which $\dim_{k+1}(G)$ is indeed exponential. For a possible further work, we leave the gap between the bounds to be reduced.20252025-12-01 12:09:15Članek v reviji176450UDK: 519.17ISSN pri članku: 1660-5446DOI: 10.1007/s00009-025-02894-3COBISS_ID: 259027203sl