×

Resolvability and strong resolvability in the direct product of graphs. (English) Zbl 1356.05038

Summary: Given a connected graph \(G\), a vertex \(w\in V(G)\) distinguishes two different vertices \(u\), \(v\) of \(G\) if the distances between \(w\) and \(u\), and between \(w\) and \(v\) are different. Moreover, \(w\) strongly resolves the pair \(u\), \(v\) 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) metric generator for \(G\) if every pair of vertices of \(G\) is (strongly resolved) distinguished by some vertex of \(W\). The smallest cardinality of a (strong) metric generator for \(G\) is called the (strong) metric dimension of \(G\). In this article we study the (strong) metric dimension of some families of direct product graphs.

MSC:

05C12 Distance in graphs
05C76 Graph operations (line graphs, products, etc.)
05C40 Connectivity
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] 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) · Zbl 1139.05314
[3] 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
[4] Chartrand G., Erwin D., Johns G.L., Zhang P.: Boundary vertices in graphs. Discrete Math. 263, 25-34 (2003) · Zbl 1020.05024
[5] Hammack R., Imrich W., Klavžar S.: Handbook of product graphs, Discrete mathematics and its applications, 2nd edn. CRC Press, Boca Raton (2011) · Zbl 1283.05001
[6] Harary F., Melter R.A.: On the metric dimension of a graph. Ars Combin. 2, 191-195 (1976) · Zbl 0349.05118
[7] Jannesari M., Omoomi B.: The metric dimension of the lexicographic product of graphs. Discrete Math. 312(22), 3349-3356 (2012) · Zbl 1252.05187
[8] Khuller S., Raghavachari B., Rosenfeld A.: Landmarks in graphs. Discrete Appl. Math. 70, 217-229 (1996) · Zbl 0865.68090
[9] Kim S.-R.: Centers of a tensor composite graph. Congr. Numer. 81, 193-203 (1991) · Zbl 0765.05093
[10] Kuziak, D., Yero, I.G., Rodríguez-Velázquez, J.A.: Closed formulae for the strong metric dimension of lexicographic product graphs. Discuss. Math. Graph Theory (2016, To appear) · Zbl 1350.05024
[11] Kuziak D., Yero I.G., Rodríguez-Velázquez J.A.: On the strong metric dimension of the strong products of graphs. Open Math. (formerly Cent. Eur. J. Math.) 13, 64-74 (2015) · Zbl 1307.05060
[12] Kuziak D., Yero I.G., Rodríguez-Velázquez J.A.: Erratum to “On the strong metric dimension of the strong products of graphs”. Open Math. 13, 209-210 (2015) · Zbl 1307.05061
[13] 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
[14] Miller D.J.: The categorical product of graphs. Can. J. Math. 20, 1511-1521 (1968) · Zbl 0167.21902
[15] Oellermann O.R., Peters-Fransen J.: The strong metric dimension of graphs and digraphs. Discrete Appl. Math. 155, 356-364 (2007) · Zbl 1111.05030
[16] Rodríguez-Velázquez J.A., Kuziak D., Yero I.G., Sigarreta J.M.: The metric dimension of strong product graphs. Carpathian J. Math. 31(2), 261-268 (2015) · Zbl 1349.05096
[17] Rodríguez-Velázquez J.A., Yero I.G., Kuziak D., Oellermann O.R.: On the strong metric dimension of Cartesian and direct products of graphs. Discrete Math. 335, 8-19 (2014) · Zbl 1298.05280
[18] Saputro S., Simanjuntak R., Uttunggadewa S., Assiyatun H., Baskoro E., Salman A., Bača M.: The metric dimension of the lexicographic product of graphs. Discrete Math. 313(9), 1045-1051 (2013) · Zbl 1263.05085
[19] Sebő A., Tannier E.: On metric generators of graphs. Math. Oper. Res. 29(2), 383-393 (2004) · Zbl 1082.05032
[20] Slater, P.J.: Leaves of trees. In: Proceeding of the 6th Southeastern conference on combinatorics, graph theory, and computing. Congr. Numer., vol. 14, pp. 549-559 (1975) · Zbl 1252.05187
[21] Vetrik, T., Ahmad, A.: Computing the metric dimension of the categorical product of some graphs. Int. J. Comput. Math. doi:10.1080/00207160.2015.1109081 · Zbl 1362.05042
[22] Weichsel P.M.: The Kronecker product of graphs. Proc. Am. Math. Soc. 13, 47-52 (1962) · Zbl 0102.38801
[23] 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
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.