The k-metric dimension

For an undirected graph $$G=(V,E)$$ G = ( V , E ) , a vertex $$\tau \in V$$ τ ∈ V separates vertices u and v (where $$u,v\in V$$ u , v ∈ V , $$u\ne v$$ u ≠ v ) if their distances to $$\tau $$ τ are not equal. Given an integer parameter $$k \ge 1$$ k ≥ 1 , a set of vertices $$L\subseteq V$$ L ⊆ V is a feasible solution, if for every pair of distinct vertices, u, v, there are at least k distinct vertices $$\tau _{1},\tau _{2},\ldots ,\tau _{k}\in L$$ τ 1 , τ 2 , … , τ k ∈ L , each separating u and v. Such a feasible solution is called a landmark set, and the k-metric dimension of a graph is the minimal cardinality of a landmark set for the parameter k. The case $$k=1$$ k = 1 is a classic problem, where in its weighted version, each vertex v has a non-negative cost, and the goal is to find a landmark set with minimal total cost. We generalize the problem for $$k \ge 2$$ k ≥ 2 , introducing two models, and we seek for solutions to both the weighted version and the unweighted version of this more general problem. In the model of all-pairs (AP), k separations are needed for every pair of distinct vertices of V, while in the non-landmarks model (NL), such separations are required only for pairs of distinct vertices in $$V \setminus L$$ V \ L . We study the weighted and unweighted versions for both models (AP and NL), for path graphs, complete graphs, complete bipartite graphs, and complete wheel graphs, for all values of $$k \ge 2$$ k ≥ 2 . We present algorithms for these cases, thus demonstrating the difference between the two new models, and the differences between the cases $$k=1$$ k = 1 and $$k \ge 2$$ k ≥ 2 .