20.500.12556/RUL-176450 Fault tolerance of metric basis can be expensive 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 $\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. metric dimension fault-tolerant metric dimension k-metric dimension true false true Angleški jezik Ni določen Članek v reviji 2025-12-01 12:09:15 2025-12-01 12:09:19 2026-06-11 11:32:16 0000-00-00 00:00:00 2025 0 0 17 str. iss. 6, art. 148 Vol. 22 Sep. 2025 0000-00-00 Zaloznikova Objavljeno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.17 1660-5446 10.1007/s00009-025-02894-3 259027203 s00009-025-02894-3_(1).pdf s00009-025-02894-3_(1).pdf 1 B8E5EE91AB2C4EB9E14C14B8437321C8 067a45a30e07c27d95eac657c171a2b23716a5a0929c76998eff760762870167 9bb19212-cea7-11f0-9328-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=222783 https://link.springer.com/article/10.1007/s00009-025-02894-3 1 ce64fe66-cea5-11f0-9328-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=222782 Fakulteta za matematiko in fiziko 0 0 0