Resolving vertices of graphs with differences

Abstract

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).