×

Comparing the metric and strong dimensions of graphs. (English) Zbl 1355.05100

Summary: 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 \(\operatorname{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 \(\operatorname{sdim}(G) \leq 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.

MSC:

05C12 Distance in graphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bodlaender, H. L.; Möhring, R. H., The pathwidth and treewidth of cographs, SIAM J. Discrete Math., 6, 181-188 (1993) · Zbl 0773.05091
[2] Brandstädt, A.; Le, V. B.; Spinrad, J. P., Graph classes: A survey, SIAM (1999) · Zbl 0919.05001
[3] Cáceres, J.; Hernando, C.; Mora, M.; Pelayo, I. M.; Puertas, M. L.; Seara, C.; Wood, D. R., On the metric dimension of Cartesian products of graphs, SIAM J. Discrete Math., 21, 2, 423-441 (2007) · Zbl 1139.05314
[4] Chartrand, G.; Eroh, L.; Johnson, M.; Oellermann, O. R., Resolvability in graphs and the metric dimension of a graph, Discrete Appl. Math., 105, 99-113 (2000) · Zbl 0958.05042
[5] Chartrand, G.; Lesniak, L.; Zhang, P., Graphs and Digraphs (2011), CRC Press, Chapman and Hall: CRC Press, Chapman and Hall Boca Raton FL
[6] Chartrand, G.; Oellermann, O. R., Applied and Algorithmic Graph Theory (1993), McGraw Hill
[7] Corneil, D. G.; Lerchs, H.; Burlingham, L. S., Complement reducible graphs, Discrete Appl. Math., 3, 163-174 (1981) · Zbl 0463.05057
[8] Epstein, L.; Levin, A.; Woeginger, G. J., The (weighted) metric dimension of graphs: hard and easy cases, Algorithmica, 72, 1130-1171 (2015) · Zbl 1320.05030
[9] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), W.H. Freeman and Company: W.H. Freeman and Company San Francisco · Zbl 0411.68039
[10] Hammer, P. L.; Maffray, F., Completely separable graphs, Discrete Appl. Math., 27, 85-99 (1990) · Zbl 0694.05060
[11] Harary, F.; Melter, R., The metric dimension of a graph, Ars Combin., 2, 191-195 (1976) · Zbl 0349.05118
[12] Hernando, C.; Mora, M.; Pelayo, I. M.; Seara, C.; Cáceres, J.; Puertas, M. L., On the metric dimension of some families of graphs, Elec. Notes Discrete Math., 22, 129-133 (2005) · Zbl 1182.05050
[13] Kang, C. X.; Yi, E., The fractional strong metric dimension of graphs, (Lecture Notes in Comput. Sci., 8287 (2013), Springer), 84-95 · Zbl 1407.05078
[14] Khuller, S.; Raghavachari, B.; Rosenfeld, A., Landmarks in graphs, Discrete Appl. Math., 70, 3, 217-229 (1996) · Zbl 0865.68090
[15] May, T. R.; Oellermann, O. R., The strong dimension of distance-hereditary graphs, J. Combin. Math. Combin. Comput., 76, 59-73 (2011) · Zbl 1233.05097
[16] Nicolai, F., Strukturelle Und Algorithmische Aspekte Distanz-Erblicher Graphen Und Verwandter Klassen (Dissertation thesis) (1994), Gerhard-Mercator-Universität Duisburg: Gerhard-Mercator-Universität Duisburg German · Zbl 0860.68080
[17] Oellermann, O. R.; Peters-Fransen, J., The strong metric dimension of graphs and digraphs, Discrete Appl. Math., 115, 356-364 (2007) · Zbl 1111.05030
[18] Rodríguez-Velázquez, J. A.; Yero, I. G.; Kuziak, D.; Oellermann, O. R., On the strong metric dimension of Cartesian and direct product graphs, Discrete Appl. Math., 335, 8-19 (2014) · Zbl 1298.05280
[19] Sebő, A.; Tannier, E., On metric generators or graphs, Math. Oper. Res., 29, 2, 383-393 (2004) · Zbl 1082.05032
[20] Slater, P. J., Leaves of trees, Congr. Numer., 14, 549-559 (1975)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.