×

On the strong metric dimension of Cartesian and direct products of graphs. (English) Zbl 1298.05280

Summary: Let \(G\) be a connected graph. A vertex \(w\) strongly resolves 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 metric dimension of \(G\). It is known that the problem of computing the strong metric dimension of a graph is NP-hard. In this paper we obtain closed formulae for the strong metric dimension of several families of Cartesian products of graphs and direct products of graphs.

MSC:

05C76 Graph operations (line graphs, products, etc.)
05C75 Structural characterization of families of graphs
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Brešar, B.; Klavžar, S.; Tepeh Horvat, A., On the geodetic number and related metric sets in Cartesian product graphs, Discrete Math., 308, 5555-5561 (2008) · Zbl 1200.05060
[2] Brigham, R. C.; Chartrand, G.; Dutton, R. D.; Zhang, P., Resolving domination in graphs, Math. Bohem., 128, 1, 25-36 (2003) · Zbl 1010.05048
[3] Cáceres, J.; Hernando, C.; Mora, M.; Pelayo, I. M.; Puertas, M. L., On the metric dimension of infinite graphs, Discrete Appl. Math., 160, 18, 2618-2626 (2012) · Zbl 1254.05051
[4] Cáceres, J.; Hernando, C.; Mora, M.; Pelayo, I. M.; Puertas, M. L.; Seara, C., On the metric dimension of some families of graphs, Electron. Notes Discrete Math., 22, 129-133 (2005) · Zbl 1182.05050
[5] 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., 21, 2, 273-302 (2007)
[6] Cáceres, J.; Puertas, M. L.; Hernando, C.; Mora, M.; Pelayo, I. M.; Seara, C., Searching for geodetic boundary vertex sets, Electron. Notes Discrete Math., 19, 25-31 (2005) · Zbl 1136.05309
[7] Chappell, G.; Gimbel, J.; Hartman, C., Bounds on the metric and partition dimensions of a graph, Ars Combin., 88, 349-366 (2008) · Zbl 1224.05133
[8] Chartrand, G.; Eroh, L.; Johnson, M. A.; Oellermann, O. R., Resolvability in graphs and the metric dimension of a graph, Discrete Appl. Math., 105, 99-113 (2000) · Zbl 0958.05042
[9] Chartrand, G.; Erwin, D.; Johns, G. L.; Zhang, P., Boundary vertices in graphs, Discrete Math., 263, 25-34 (2003) · Zbl 1020.05024
[10] Chartrand, G.; Poisson, C.; Zhang, P., Resolvability and the upper dimension of graphs, Comput. Math. Appl., 39, 19-28 (2000) · Zbl 0953.05021
[11] Chartrand, G.; Salehi, E.; Zhang, P., The partition dimension of a graph, Aequationes Math., 59, 1-2, 45-54 (2000) · Zbl 0939.05029
[12] Egerváry, J., Matrixok kombinatorius tulajdonságairol, Mat. Fiz. Lapok, 38, 16-28 (1931)
[13] Fehr, M.; Gosselin, S.; Oellermann, O. R., The partition dimension of Cayley digraphs, Aequationes Math., 71, 1-18 (2006) · Zbl 1086.05024
[14] Gallai, T., Über extreme Punkt- und Kantenmengen, Ann. Univ. Sci. Budapest Eötvós Sect. Math., 2, 133-138 (1959) · Zbl 0094.36105
[15] Hall, P., On representation of subsets, J. Lond. Math. Soc., 10, 26-30 (1935) · JFM 61.0067.01
[16] Harary, F.; Melter, R. A., On the metric dimension of a graph, Ars Combin., 2, 191-195 (1976) · Zbl 0349.05118
[17] Haynes, T. W.; Henning, M.; Howard, J., Locating and total dominating sets in trees, Discrete Appl. Math., 154, 1293-1300 (2006) · Zbl 1091.05051
[18] Hernando, C.; Mora, M.; Pelayo, I. M.; Seara, C.; Wood, D. R., Extremal graph theory for metric dimension and diameter, Electron. J. Combin., 17, 1, R30 (2010) · Zbl 1219.05051
[19] Imrich, W.; Klavzar, S., Product Graphs: Structure and Recognition (2000), Wiley: Wiley New York
[20] Jha, P. K.; Slutzki, G., Independence numbers of product graphs, Appl. Math. Lett., 7, 4, 91-94 (1994) · Zbl 0811.05033
[21] Johnson, M. A., Structure-activity maps for visualizing the graph variables arising in drug design, J. Biopharm. Statist., 3, 203-236 (1993) · Zbl 0800.92106
[22] Johnson, M. A., Browsable structure-activity datasets, (Carbó-Dorca, R.; Mezey, P., Advances in Molecular Similarity (1998), JAI Press: JAI Press Connecticut), 153-170
[23] Khuller, S.; Raghavachari, B.; Rosenfeld, A., Landmarks in graphs, Discrete Appl. Math., 70, 217-229 (1996) · Zbl 0865.68090
[24] König, D.; mátrixok, Gráfok és, Mat. Fiz. Lapok, 38, 116-119 (1931)
[25] Kratica, J.; Kovačević-Vujčić, V.; Čangalović, M.; Stojanović, M., Minimal doubly resolving sets and the strong metric dimension of Hamming graphs, Appl. Anal. Discrete Math., 6, 63-71 (2012) · Zbl 1289.05400
[26] 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., 161, 1022-1027 (2013) · Zbl 1262.05133
[27] 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
[28] Melter, R. A.; Tomescu, I., Metric bases in digital geometry, Comput. Vis. Graph. Image Process., 25, 113-121 (1984) · Zbl 0591.51023
[29] Miller, D. J., The categorical product of graphs, Canad. J. Math., 20, 1511-1521 (1968) · Zbl 0167.21902
[30] Oellermann, O. R.; Peters-Fransen, J., The strong metric dimension of graphs and digraphs, Discrete Appl. Math., 155, 356-364 (2007) · Zbl 1111.05030
[31] Okamoto, F.; Phinezyn, B.; Zhang, P., The local metric dimension of a graph, Math. Bohem., 135, 3, 239-255 (2010) · Zbl 1224.05152
[32] Saenpholphat, V.; Zhang, P., Conditional resolvability in graphs: a survey, Int. J. Math. Math. Sci., 38, 1997-2017 (2004) · Zbl 1061.05028
[33] Sebő, A.; Tannier, E., On metric generators of graphs, Math. Oper. Res., 29, 2, 383-393 (2004) · Zbl 1082.05032
[34] Slater, P. J., Leaves of trees, Proceeding of the 6th Southeastern Conference on Combinatorics, Graph Theory, and Computing, vol. 14, 549-559 (1975)
[35] Slater, P. J., Dominating and reference sets in a graph, J. Math. Phys. Sci., 22, 4, 445-455 (1988) · Zbl 0656.05057
[36] Špacapan, S., The \(k\)-independence number of direct products of graphs and Hedetniemi’s conjecture, European J. Combin., 32, 1377-1383 (2011) · Zbl 1284.05204
[37] Tomescu, I., Discrepancies between metric and partition dimension of a connected graph, Discrete Math., 308, 5026-5031 (2008) · Zbl 1184.05033
[38] Valencia-Pabon, M.; Vera, J., Independence and coloring properties of direct products of some vertex-transitive graphs, Discrete Math., 306, 2275-2281 (2006) · Zbl 1111.05040
[39] Vizing, V. G., The Cartesian product of graphs, Vychisl. Sistemy, 9, 30-43 (1963), (in Russian)
[40] Yero, I. G.; Kuziak, D.; Rodríguez-Velázquez, J. A., On the metric dimension of corona product graphs, Comput. Math. Appl., 61, 9, 2793-2798 (2011) · Zbl 1221.05252
[41] Yero, I. G.; Rodríguez-Velázquez, J. A., A note on the partition dimension of Cartesian product graphs, Appl. Math. Comput., 217, 7, 3571-3574 (2010) · Zbl 1215.05146
[42] Zhang, H., Independent sets in direct products of vertex-transitive graphs, J. Combin. Theory Ser. B, 102, 3, 832-838 (2012) · Zbl 1251.05130
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.