### 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 □ H. We prove that the metric dimension of G□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 □ 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□G is unbounded.

Original language | English |
---|---|

Pages (from-to) | 423-441 |

Number of pages | 19 |

Journal | SIAM Journal on Discrete Mathematics |

Volume | 21 |

Issue number | 2 |

DOIs | |

Publication status | Published - 2007 |

Externally published | Yes |

## Cite this

Cáceres, J., Hernando, C., Mora, M., Pelayo, I. M., Puertas, M. A. L., Seara, C., & Wood, D. R. (2007). On the metric dimension of Cartesian products of graphs.

*SIAM Journal on Discrete Mathematics*,*21*(2), 423-441. https://doi.org/10.1137/050641867