Resolving Sets Tolerant to Failures in Three-Dimensional Grids
Ver/ abrir
Use este enlace para citar
http://hdl.handle.net/2183/31517
A non ser que se indique outra cousa, a licenza do ítem descríbese como Attribution 4.0 International (CC BY 4.0)
Coleccións
- GI-XDA - Artigos [13]
- OpenAIRE [331]
Metadatos
Mostrar o rexistro completo do ítemTítulo
Resolving Sets Tolerant to Failures in Three-Dimensional GridsData
2022Cita bibliográfica
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
Resumo
[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.
Palabras chave
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
Versión do editor
Dereitos
Attribution 4.0 International (CC BY 4.0)
ISSN
1660-5454