×

The strong dimension of distance-hereditary graphs. (English) Zbl 1233.05097

Summary: 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. We present efficient solutions for finding the strong dimension of distance-hereditary graphs, a class of graphs that contains the trees.

MSC:

05C12 Distance in graphs
05C85 Graph algorithms (graph-theoretic aspects)
PDFBibTeX XMLCite