Fault tolerance of metric basis can be expensive

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

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.

• Jezik: Angleški jezik
• Ključne besede: metric dimension, fault-tolerant metric dimension, k-metric dimension
• Vrsta gradiva: Članek v reviji
• Tipologija: 1.01 - Izvirni znanstveni članek
• Organizacija: FMF - Fakulteta za matematiko in fiziko
• Status publikacije: Objavljeno
• Različica publikacije: Objavljena publikacija
• Datum objave: 01.09.2025
• Leto izida: 2025
• Št. strani: 17 str.
• Številčenje: Vol. 22, iss. 6, art. no. 148
• PID: 20.500.12556/RUL-176450
• UDK: 519.17
• ISSN pri članku: 1660-5446
• DOI: 10.1007/s00009-025-02894-3
• COBISS.SI-ID: 259027203
• Datum objave v RUL: 01.12.2025

Gradivo je del revije

• Naslov: Mediterranean journal of mathematics
• Skrajšan naslov: Mediterr. j. math.
• Založnik: Springer
• ISSN: 1660-5446
• COBISS.SI-ID: 13561433

Licence

• Licenca: CC BY 4.0, Creative Commons Priznanje avtorstva 4.0 Mednarodna
• Povezava: http://creativecommons.org/licenses/by/4.0/deed.sl
• Opis: To je standardna licenca Creative Commons, ki daje uporabnikom največ možnosti za nadaljnjo uporabo dela, pri čemer morajo navesti avtorja.