On the metric dimension of Cartesian powers of a graph
Preprint
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\H{o}s and R\'enyi and the upper bounds developed subsequently by Lindstr\"om, Chv\'atal, Kabatianski, Lebedev and Thorpe.
Keywords
All Related Versions
This publication has 6 references indexed in Scilit:
- On Metric Generators of GraphsMathematics of Operations Research, 2004
- An information-theoretic method in combinatorial theoryJournal of Combinatorial Theory, Series A, 1977
- Determinants on semilatticesProceedings of the American Mathematical Society, 1969
- Determination of a Subset from Certain Combinatorial PropertiesCanadian Journal of Mathematics, 1966
- On a Combinatorial Problem in Number TheoryCanadian Mathematical Bulletin, 1965
- On a Problem in Additive Number TheoryAnnals of Mathematics, 1948