Resolving Sets Tolerant to Failures in Three-Dimensional Grids
View/ Open
Use this link to cite
http://hdl.handle.net/2183/31517
Except where otherwise noted, this item's license is described as Attribution 4.0 International (CC BY 4.0)
Collections
- GI-XDA - Artigos [13]
- OpenAIRE [368]
Metadata
Show full item recordTitle
Resolving Sets Tolerant to Failures in Three-Dimensional GridsDate
2022Citation
Mora, M., Souto-Salorio, M.J. & Tarrío-Tobar, A.D. Resolving sets tolerant to failures in three-dimensional grids. Mediterr. J. Math. 19, 188 (2022). https://doi.org/10.1007/s00009-022-02096-1
Abstract
[Abstract] An ordered set S of vertices of a graph G is a resolving set for G if every vertex is uniquely determined by its vector of distances to the vertices in S. The metric dimension of G is the minimum cardinality of a resolving set. In this paper we study resolving sets tolerant to several failures in three-dimensional grids. Concretely, we seek for minimum cardinality sets that are resolving after removing any k vertices from the set. This is equivalent to finding (k+1)-resolving sets, a generalization of resolving sets, where, for every pair of vertices, the vector of distances to the vertices of the set differs in at least k+1 coordinates. This problem is also related with the study of the (k+1)-metric dimension of a graph, defined as the minimum cardinality of a (k+1)-resolving set. In this work, we first prove that the metric dimension of a three-dimensional grid is 3 and establish some properties involving resolving sets in these graphs. Secondly, we determine the values of k≥1 for which there exists a (k+1)-resolving set and construct such a resolving set of minimum cardinality in almost all cases.
Keywords
Resolving set
Metric dimension
k-resolving set
k-metric dimension
Fault-tolerant
Three-dimensional grid
Metric dimension
k-resolving set
k-metric dimension
Fault-tolerant
Three-dimensional grid
Editor version
Rights
Attribution 4.0 International (CC BY 4.0)
ISSN
1660-5454