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≥2 vertices, and let M be the distance matrix of G. We prove that if there exists w∈Zq such that ∑iwi=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/logqn. 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.
Original language | English (US) |
---|---|
Pages (from-to) | 1-14 |
Number of pages | 14 |
Journal | Journal of Combinatorial Theory. Series A |
Volume | 165 |
DOIs | |
State | Published - Jul 2019 |
Externally published | Yes |
Keywords
- Cartesian product
- Metric dimension
- Möbius function
- Resolving set
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics