Let G be a connected graph. A vertex w ∈ V.G/ strongly resolves two vertices u,v ∈ V.G/ if there exists some shortest u-w path containing v or some shortest v-w path containing u. A set S of vertices is a strong resolving set for G if every pair of vertices of G is strongly resolved by some vertex of S. The smallest cardinality of a strong resolving set for G is called the strong metric dimension of G. It is well known that the problem of computing this invariant is NP-hard. In this paper we study the problem of finding exact values or sharp bounds for the strong metric dimension of strong product graphs and express these in terms of invariants of the factor graphs.
@article{bwmeta1.element.doi-10_1515_math-2015-0007,
author = {Dorota Kuziak and Ismael G. Yero and Juan A. Rodr\'\i guez-Vel\'azquez},
title = {On the strong metric dimension of the strong products of graphs},
journal = {Open Mathematics},
volume = {13},
year = {2015},
zbl = {1307.05061},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_1515_math-2015-0007}
}
Dorota Kuziak; Ismael G. Yero; Juan A. Rodríguez-Velázquez. On the strong metric dimension of the strong products of graphs. Open Mathematics, Tome 13 (2015) . http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_1515_math-2015-0007/
[1] Cáceres J. , Hernando C., Mora M., Pelayo I. M., Puertas M. L., Boundary-type sets and product operators in graphs, In: VII Jornadas de Matemática Discreta y Algorítmica, Castro Urdiales, Cantabria, Spain, July 2010 | Zbl 1207.05043
[2] Cáceres J., Hernando C., Mora M., Pelayo I. M., Puertas M. L., Seara C., Wood D. R., On the metric dimension of Cartesian product of graphs, SIAM J. Discrete Math., 2007, 21(2), 273–302 [WoS] | Zbl 1139.05314
[3] Cˇ ižek N., Klavžar S., On the chromatic number of the lexicographic product and the Cartesian sum of graphs, Discrete Math., 1994, 134(1-3), 17–24
[4] Feng M., Wang K., On the metric dimension and fractional metric dimension of the hierarchical product of graphs, Appl. Anal. Discrete Math., 2013, 7, 302–313 [WoS][Crossref] | Zbl 06451378
[5] Gallai T., Uber Extreme Punkt-und Kantenmengen, Ann. Univ. Sci. Budapest Eötvös Sect. Math., 1959, 2, 133–138 (in German)
[6] Geller D., Stahl S., The chromatic number and other functions of the lexicographic product, J. Combin. Theory Ser. B, 1975, 19, 87–95 | Zbl 0282.05114
[7] Hales R. S., Numerical invariants and the strong product of graphs, J. Combin. Theory Ser. B, 1973, 15, 146–155 | Zbl 0247.05122
[8] Hammack R., Imrich W., Klavžar S., Handbook of Product Graphs, Second edition. With a foreword by Peter Winkler. Discrete Math. Appl. (Boca Raton), CRC Press, Boca Raton, FL, 2011 | Zbl 1283.05001
[9] Harary F., Melter R. A., On the metric dimension of a graph, Ars Combin., 1976, 2, 191–195 | Zbl 0349.05118
[10] Jannesari M., Omoomi B., The metric dimension of the lexicographic product of graphs, Discrete Math. 2012, 312(22), 3349–3356 | Zbl 1252.05187
[11] Jha P. K., Slutzki G., Independence numbers of product graphs, Appl. Math. Lett., 1994, 7(4), 91–94 [Crossref] | Zbl 0811.05033
[12] Johnson M. A., Structure-activity maps for visualizing the graph variables arising in drug design, J. Biopharm. Statist., 1993, 3, 203–236 [Crossref] | Zbl 0800.92106
[13] Johnson M. A., Browsable structure-activity datasets, In: Advances in Molecular Similarity, R. Carbó–Dorca and P. Mezey, eds., JAI Press Connecticut, 1998, 153–170
[14] Khuller S., Raghavachari B., Rosenfeld A., Landmarks in graphs, Discrete Appl. Math., 1996, 70, 217–229 | Zbl 0865.68090
[15] Kratica J., Kovacˇevic´-Vujcˇic´ V., Cˇ angalovic´ M., Stojanovic´ M., Minimal doubly resolving sets and the strong metric dimension of Hamming graphs, Appl. Anal. Discrete Math., 2012, 6, 63–71 [Crossref][WoS]
[16] Kuziak D., Yero I. G., Rodríguez-Velázquez J. A., On the strong metric dimension of corona product graphs and join graphs, Discrete Appl. Math., 2013, 161(7-8), 1022–1027 [WoS] | Zbl 1262.05133
[17] Melter R. A., Tomescu I., Metric bases in digital geometry, Computer Vision, Graphics, and Image Processing, 1984, 25, 113–121 | Zbl 0591.51023
[18] Oellermann O. R., Peters-Fransen J., The strong metric dimension of graphs and digraphs, Discrete Appl. Math., 2007, 155, 356–364 [WoS] | Zbl 1111.05030
[19] Ore, O., Theory of graphs, Amer. Math. Soc. Colloq. Publ., 38, Amer. Math. Soc., Providence, R.I., 1962 | Zbl 0105.35401
[20] Rodríguez-Velázquez J. A., Kuziak D., Yero I. G., Sigarreta J. M., The metric dimension of strong product graphs, Carpathian J. Math. (in press), preprint available at http://arxiv.org/abs/1305.0363 | Zbl 06582104
[21] Saputro S., Simanjuntak R., Uttunggadewa S., Assiyatun H., Baskoro E., Salman A., Baˇca M., The metric dimension of the lexicographic product of graphs, Discrete Math., 2013, 313(9), 1045–1051 | Zbl 1263.05085
[22] Scheinerman E., Ullman D., Fractional Graph Theory. A rational approach to the theory of graphs. With a foreword by Claude Berge, Wiley-Intersci. Ser. Discrete Math. Optim., A Wiley-Interscience Publication. John Wiley & Sons, Inc., New York, 1997 | Zbl 0891.05003
[23] Seb˝o A., Tannier E., On metric generators of graphs, Math. Oper. Res., 2004, 29(2), 383–393 [Crossref] | Zbl 1082.05032
[24] Slater P. J., Leaves of trees, In: Proceeding of the 6th Southeastern Conference on Combinatorics, Graph Theory, and Computing. Congr. Numer., 1975, 14, 549–559
[25] Yero I. G., Kuziak D., Rodríguez-Velázquez J. A., On the metric dimension of corona product graphs, Comput. Math. Appl., 2011, 61(9), 2793–2798[WoS] | Zbl 1221.05252