On the Metric Dimension of Cartesian Products of Graphs

By J. Cáceres, C. Hernando, M. Mora, I. Pelayo, M. L. Puertas, C. Seara, David R. Wood. SIAM Journal on Discrete Mathematics, 2005

519 citations recorded by the source corpus.

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.

Subfields: Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/d40a307ec5db6529798b4d38ad9ed11b0e8de66d

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

Citations in the corpus

Base size, metric dimension and other invariants of groups and graphs (2011, background): “[30] have also studied the problem, for H(2,m) (the square lattice graphs).”
Network Discovery and Verification (2005, background): “See also [23] for further results on the metric”
The local metric dimension of a graph (2010, methodology): “In [4] bounds (or exact values) have been established on lmd(G×H) for many well-known classes of graphs G and H .”
The k-metric dimension of a graph (2013, result): “This invariant was studied further in a number of other papers including for example, [3, 4, 5, 7, 8, 10, 16, 17, 21, 22, 23].”
Metric-based resolvability of polycyclic aromatic hydrocarbons (2021, methodology): “Partition dimension also has many applications in various real-world applications, such as strategies, coding, and decoding of mastermind games [9], the popular Djokovic–Winkler relation [4], and the procedure of verifying and discovering a network [3].”