Comparing the metric and strong dimensions of graphs

Let G be a graph and u, v be any two distinct vertices of G. A vertex w of G resolves u and v if the distance between u and w does not equal the distance between v and w. A set W of vertices of G is a resolving set for G if every pair of vertices of G is resolved by some vertex of W. The minimum cardinality of a resolving set for G is the metric dimension, denoted by dim(G). If G is a connected graph, then a vertex w strongly resolves two vertices u and v if there is a shortest u-w path containing v or a shortest v-w path containing u. A set S of vertices is a strong resolving set for G if every pair of vertices is strongly resolved by some vertex of S and the minimum cardinality of a strong resolving set is called the strong dimension of G and is denoted by sdim(G). Both the problem of finding the metric dimension and the problem of finding the strong dimension of a graph are known to be NP-hard. It is known that the strong dimension can be polynomially transformed to the vertex covering problem for which good approximation algorithms are known. The metric dimension is a lower bound for the strong dimension. In this paper we compare the metric and strong dimensions of graphs. We describe all trees for which these invariants are the same and determine the class of trees for which the difference between these invariants is a maximum. We observe that there is no linear upper bound for the strong dimension of trees in terms of the metric dimension. For cographs we show that sdim(G) <= 3 dim(G) and that this bound is asymptotically sharp. It is known that the problem of finding the metric dimension of split graphs is NP-hard. We show that the strong dimension of connected split graphs can be found in polynomial time. (C) 2016 Elsevier B.V. All rights reserved.