On the metric dimension of Cartesian powers of a graph

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:165

Article

Jiang, Zilin^1,3  Polyanskii, Nikita^2,3 

[1] MIT, Dept Math, Cambridge, MA 02139 USA

[2] Skolkovo Inst Sci & Technol, CDISE, Moscow 121205, Russia

[3] Technion Israel Inst Technol, Haifa, Israel

关键词: Resolving set;    Metric dimension;    Cartesian product;    Mobius function;   

DOI  :  10.1016/j.jcta.2019.01.002

来源: Elsevier

【 摘 要 】

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 is an element of Z(q) such that Sigma(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 Erdos and Renyi and the upper bounds developed subsequently by Lindstrom, Chvatal, Kabatianski, Lebedev and Thorpe. (C) 2019 Elsevier Inc. All rights reserved.

【 授权许可】

Free