The metric dimension of strong product graphs
DEPARTAMENT D’ENGINYERIA INFORMATICA I MATEMATIQUES UNIVERSITAT ROVIRA I VIRGILI AV. PAISOS CATALANS 26, 43007 TARRAGONA, SPAIN E-mail address: [email protected], Juan Alberto Rodriguez-Velazquez, Dorota Kuziak, DEPARTAMENT D’ENGINYERIA INFORMATICA I MATEMATIQUES UNIVERSITAT ROVIRA I VIRGILI AV. PAISOS CATALANS 26, 43007 TARRAGONA, SPAIN E-mail address: [email protected], Ismael G. Yero, DEPARTAMENTO DE MATEMATICAS, ESCUELA POLITECNICA SUPERIOR DE ALGECIRAS UNIVERSIDAD DE CADIZ AV. RAMON PUYOL S/N, 11202 ALGECIRAS, SPAIN E-mail address: [email protected], José M. Sigarreta, UNIVERSIDAD AUTONOMA DE GUERRERO FACULTAD DE MATEMATICAS CARLOS E. ADAME 5, COL. LA GARITA, ACAPULCO, GUERRERO, MEXICO E-mail address: [email protected] · Carpathian Journal of Mathematics · 2015
For an ordered subset S = {s1, s2, . . . sk} of vertices in a connected graph G, the metric representation of a vertex u with respect to the set S is the k-vector r(u|S) = (dG(v, s1), dG(v, s2), . . . , dG(v, sk)), where dG(x, y) represents the distance between the vertices x and y. The set S is a metric generator for G if every two different vertices of G have distinct metric representations with respect to S. A minimum metric generator is called a metric basis for G and its cardinality, dim(G), the metric dimension of G. It is well known that the problem of finding the metric dimension of a graph is NP-Hard. In this paper we obtain closed formulae and tight bounds for the metric dimension of strong product graphs.