Nikita Polyansky – On the metric dimension of Cartesian powers of a graph


Event Details

  • Date:

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 q2 vertices, and let M be the distance matrix of G. We prove that if there exists wZq such that ∑_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 bound by Chv\’atal. The main tool is the M\”obius function of a certain partially ordered set on N.