Fault Tolerance of Metric Basis Can Be Expensive
Martin Knor, Jelena Sedlar, Riste Škrekovski · Mediterranean Journal of Mathematics · 2025
Abstract 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)$$ 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)$$ ftdim ( G ) is the cardinality of a smallest resolving set S such that $$S\setminus \{s\}$$ S \ { s } remains a resolving set of G for every $$s\in S$$ s ∈ 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)$$ ftdim ( G ) which is exponential in terms of $$\textrm{dim}(G),$$ dim ( G ) , i.e. $$\textrm{ftdim}(G)\le \textrm{dim}(G)(1+2\cdot 5^{\textrm{dim}(G)-1}).$$ ftdim ( G ) ≤ dim ( G ) ( 1 + 2 · 5 dim ( G ) - 1 ) . In this paper, we construct graphs G with $$\textrm{ftdim}(G)=\textrm{dim}(G)+2^{\textrm{dim}(G)-1}$$ ftdim ( G ) = dim ( G ) + 2 dim ( G ) - 1 for any value of $$\textrm{dim}(G)$$ 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)$$ dim k + 1 ( G ) in terms of $$\textrm{dim}_{k}(G),$$ dim k ( G ) , and then we show that there exists a graph for which