The strong metric dimension of graphs and digraphs

Let G   be a connected (di)graph. A vertex ww is said to strongly resolve a pair u,vu,v of vertices of G   if there exists some shortest uu–ww path containing vv or some shortest vv–ww path containing u. A set W of vertices is a strong resolving set for G if every pair of vertices of G is strongly resolved by some vertex of W. The smallest cardinality of a strong resolving set for G is called the strong dimension of G. It is shown that the problem of finding the strong dimension of a connected graph can be transformed to the problem of finding the vertex covering number of a graph. Moreover, it is shown that computing this invariant is NP-hard. Related invariants for directed graphs are defined and studied.