Fault tolerance of metric basis can be expensive

Knor, Martin (author), Sedlar, Jelena (author), Škrekovski, Riste (author)

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.

• Language: English
• Keywords: metric dimension, fault-tolerant metric dimension, k-metric dimension
• Work type: Article
• Typology: 1.01 - Original Scientific Article
• Organization: FMF - Faculty of Mathematics and Physics
• Publication status: Published
• Publication version: Version of Record
• Publication date: 01.09.2025
• Year: 2025
• Number of pages: 17 str.
• Numbering: Vol. 22, iss. 6, art. no. 148
• PID: 20.500.12556/RUL-176450
• UDC: 519.17
• ISSN on article: 1660-5446
• DOI: 10.1007/s00009-025-02894-3
• COBISS.SI-ID: 259027203
• Publication date in RUL: 01.12.2025

Record is a part of a journal

• Title: Mediterranean journal of mathematics
• Shortened title: Mediterr. j. math.
• Publisher: Springer
• ISSN: 1660-5446
• COBISS.SI-ID: 13561433

Licences

• License: CC BY 4.0, Creative Commons Attribution 4.0 International
• Link: http://creativecommons.org/licenses/by/4.0/
• Description: This is the standard Creative Commons license that gives others maximum freedom to do what they want with the work as long as they credit the author.