×

The strong metric dimension of graphs and digraphs. (English) Zbl 1111.05030

Summary: Let \(G\) be a connected (di)graph. A vertex \(w\) is said to strongly resolve a pair \(u,v\) of vertices of \(G\) if there exists some shortest \(u\)-\(w\) path containing \(v\) or some shortest \(v\)-\(w\) 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.

MSC:

05C12 Distance in graphs
05C20 Directed graphs (digraphs), tournaments
05C85 Graph algorithms (graph-theoretic aspects)
05C90 Applications of graph theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] 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
[2] Chartrand, G.; Lesniak, L., Graphs & Digraphs (2004), Chapman and Hall: Chapman and Hall London
[3] Chartrand, G.; Raines, M.; Zhang, P., The directed distance dimension of oriented graphs, Math. Bohemica, 125, 155-168 (2000) · Zbl 0963.05045
[4] Chartrand, G.; Raines, M.; Zhang, P., On the dimension of oriented graphs, Utilitas Math., 60, 139-151 (2001) · Zbl 1011.05020
[5] I.K. Evans, Evolutionary algorithms for vertex cover, Evolutionary Programming VII, Proceeding of 7th International Conference EP98.; I.K. Evans, Evolutionary algorithms for vertex cover, Evolutionary Programming VII, Proceeding of 7th International Conference EP98.
[6] Fehr, M.; Gosselin, S.; Oellermann, O., Metric dimension of Cayley digraphs, Discrete Math., 306, 31-41 (2006) · Zbl 1085.05034
[7] Gallai, T., Über extreme Punkt und Kantenmengen, Ann. Univ. Sci. Budapest, Eötvös Sect. Math., 2, 133-138 (1959) · Zbl 0094.36105
[8] Gallian, J. A., Contemporary Abstract Algebra (2002), Houghton Mifflin Company: Houghton Mifflin Company New York · Zbl 1051.00001
[9] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), Freeman: Freeman New York · Zbl 0411.68039
[10] Harary, F.; Melter, R. A., On the metric dimension of a graph, Ars Combin., 2, 191-195 (1976) · Zbl 0349.05118
[11] Hochbaum, D. S., Approximation Algorithms for NP-hard Problems (1997), PWS Publishing Company: PWS Publishing Company PS
[12] S. Khuller, B. Raghavachari, A. Rosenfeld, Localization in graphs, Technical Report CS-TR-3326, University of Maryland at College Park, 1994.; S. Khuller, B. Raghavachari, A. Rosenfeld, Localization in graphs, Technical Report CS-TR-3326, University of Maryland at College Park, 1994. · Zbl 0865.68090
[13] R. Motwani, Lecture notes on approximation algorithms—volume 1, Technical Report, Department of Computer Science, Stanford University, 1992.; R. Motwani, Lecture notes on approximation algorithms—volume 1, Technical Report, Department of Computer Science, Stanford University, 1992.
[14] Slater, P. J., Leaves of trees, Congress. Numer., 14, 549-559 (1975)
[15] Slater, P. J., Dominating and reference sets in a graph, J. Math. Phys. Sci., 22, 445-455 (1988) · Zbl 0656.05057
[16] Oellermann, O.; Peters-Fransen, J., Metric dimension of Cartesian products of graphs, Utilitas Math., 69, 33-41 (2006) · Zbl 1109.05041
[17] Sebö, A.; Tannier, E., On metric generators of graphs, Math. Oper. Res., 29, 2, 383-393 (2004) · Zbl 1082.05032
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.