On the metric dimension of Cartesian powers of a graph

Abstract

A set of vertices $S$ resolves a graph if every vertex is uniquely determined by its vector of distances to the vertices in $S$. The metric dimension of a graph is the minimum cardinality of a resolving set of the graph. Fix a connected graph $G$ on $q\ge 2$ vertices, and let $M$ be the distance matrix of $G$. We prove that if there exists $w\in {\mathbb{Z}}^q$ such that ${\sum }_i{w}_i=0$ and the vector $Mw$, after sorting its coordinates, is an arithmetic progression with nonzero common difference, then the metric dimension of the Cartesian product of $n$ copies of $G$ is $(2+o(1))n/{\log }_{q}n$. In the special case that $G$ is a complete graph, our results close the gap between the lower bound attributed to Erdős and Rényi and the upper bounds developed subsequently by Lindström, Chvátal, Kabatianski, Lebedev and Thorpe.

12 pages, 1 figure, 1 table, accepted to J. Comb. Theory A, corrections suggested by the referees have been incorporated

Cited by in corpus (8)

• A bridge between the minimal doubly resolving set problem in (folded) hypercubes and the coin weighing problem
• Recovery from Non-Decomposable Distance Oracles
• Resolving sets tolerant to failures in three-dimensional grids
• Metric dimension, minimal doubly resolving sets and the strong metric dimension for jellyfish graph and cocktail party graph
• On Vertices Contained in All or in No Metric Basis
• Completeness-resolvable graphs
• Maker-Breaker resolving game
• The Query Complexity of Mastermind with ${\ell }_p$ Distances