On the metric dimension of Cartesian powers of a graph

Zilin Jiang, Nikita Polyanskii

    Research output: Contribution to journalArticlepeer-review

    11 Citations (Scopus)


    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/logq⁡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.

    Original languageEnglish
    Pages (from-to)1-14
    Number of pages14
    JournalJournal of Combinatorial Theory. Series A
    Publication statusPublished - Jul 2019


    • Cartesian product
    • Metric dimension
    • Möbius function
    • Resolving set


    Dive into the research topics of 'On the metric dimension of Cartesian powers of a graph'. Together they form a unique fingerprint.

    Cite this