The metric dimension of Cartesian products of graphs

Abstract

A vertex x in a graph G is said to resolve a pair u, v of vertices of G if the distance from u to x does not equal the distance from v to x. A set S of vertices of G is a resolving set for G if every pair of vertices of G is resolved by some vertex of S. The smallest cardinality of a resolving set for G, denoted by dim(G), is called the metric dimension for G. Bounds on the metric dimension of the Cartesian product of cycles and graphs are established and exact values are given when both graphs are cycles.