On the Metric Dimension of Cartesian Products of Graphs

Abstract

A set of vertices S resolves a graph G if every vertex is uniquely determined by its vector of distances to the vertices in S. The metric dimension of G is the minimum cardinality of a resolving set of G. This paper studies the metric dimension of cartesian products $G\,\square\,H$. We prove that the metric dimension of $G\,\square\,G$ is tied in a strong sense to the minimum order of a so‐called doubly resolving set in G. Using bounds on the order of doubly resolving sets, we establish bounds on $G\,\square\,H$ for many examples of G and H. One of our main results is a family of graphs G with bounded metric dimension for which the metric dimension of $G\,\square\,G$ is unbounded.