RT journal article
T1 Resolving vertices of graphs with differences
A1 Peterin, I.
A1 Sedlar, J.
A1 Škrekovski, R.
A1 González Yero, Ismael
A2 Matemáticas
K1 05C12
K1 Weak k-metric dimension
K1 Weak k-resolving set
AB The classical (vertex) metric dimension of a graph G is defined as the cardinality of a smallest set S⊆V(G) such that any two vertices x and y from G have different distances to least one vertex from S. The k-metric dimension is a generalization of that notion where it is required that any pair of vertices has different distances to at least k vertices from S. In this paper, we introduce the weak k-metric dimension of a graph G, which is defined as the cardinality of a smallest set of vertices S such that the sum of the distance differences from any pair of vertices to all vertices of S is at least k. This dimension is “stronger” than the classical metric dimension, yet “weaker” than k-metric dimension, and it can be formulated as an ILP problem. The maximum k for which the weak k-metric dimension is defined is denoted by κ(G). We first prove several properties of the weak k-metric dimension regarding the presence of true or false twin vertices in a graph. Using those properties, the κ(G) is found for some basic graph classes, such as paths, stars, cycles, and complete (bipartite) graphs. We also find κ(G) for trees and grid graphs using the observation that the distance difference increases by the increase of the cardinality of a set S. For all these graph classes we further establish the exact value of the weak k-metric dimension for all k≤κ(G).
PB Springer Nature
SN 1807-0302
YR 2024
FD 2024
LK http://hdl.handle.net/10498/33683
UL http://hdl.handle.net/10498/33683
LA eng
NO European Commission (European Union) European Regional Development Fund (European Union) Ministerio de Ciencia e Innovación (España) Javna Agencija za Raziskovalno Dejavnost RS (Slovenia)
DS Repositorio Institucional de la Universidad de Cádiz
RD 11-nov-2026