On the metric dimension of Cartesian products of graphs

J. Cáceres, C. Hernando, Merce Mora, I. M. Pelayo, M. L. Puertas, C. Seara, D. R. Wood

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

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 languageEnglish
Title of host publicationFifth Conference on Discrete Mathematics and Computer Science (Spanish)
PublisherUniv. Valladolid, Secr. Publ. Intercamb. Ed., Valladolid
Pages195-202
Number of pages8
Volume23
Publication statusPublished - 2006
Externally publishedYes

Publication series

NameCiencias (Valladolid)
PublisherUniv. Valladolid, Secr. Publ. Intercamb. Ed., Valladolid

Cite this