Menu
Let \( G \) be a connected graph. A vertex \( r \) resolves a pair \( u,v \) of vertices of \( G \) if \( u \) and \( v \) are different distances from \( r \). A set \( R \) of vertices of \( G \) is a resolving set for \( G \) if every pair of vertices of \( G \) is resolved by some vertex of \( R \). The smallest cardinality of a resolving set is called the metric dimension of \( G \). A vertex \( r \) strongly resolves a pair \( u,v \) of vertices of \( G \) if there is some shortest \( u-r \) path that contains \( v \) or a shortest \( v-r \) path that contains \( u \). A set \( S \) of vertices of \( G \) is a strong resolving set for \( G \) if every pair of vertices of \( G \) is strongly resolved by some vertex of \( S \); and the smallest cardinality of a strong resolving set of \( G \) is called the strong dimension of \( G \). The problems of finding the metric dimension and strong dimension are NP-hard. Both the metric and strong dimension can be found efficiently for trees. In this paper, we present efficient solutions for finding the strong dimension of distance-hereditary graphs, a class of graphs that contains the trees.