Minimal doubly resolving sets and the strong metric dimension of some convex polytopes

Abstract

In this paper we consider two similar optimization problems on graphs: the strong metric dimension problem and the problem of determining minimal doubly resolving sets. We prove some properties of strong resolving sets and give an integer linear programming formulation of the strong metric dimension problem. These results are used to derive explicit expressions in terms of the dimension n, for the strong metric dimension of two classes of convex polytopes Dn and Tn. On the other hand, we prove that minimal doubly resolving sets of Dn and Tn have constant cardinality for n>7.