{
  "id": "1712.02723",
  "version": "v1",
  "published": "2017-12-07T17:09:57.000Z",
  "updated": "2017-12-07T17:09:57.000Z",
  "title": "On the metric dimension of Cartesian powers of a graph",
  "authors": [
    "Zilin Jiang",
    "Nikita Polyanskii"
  ],
  "comment": "12 pages, 1 figure",
  "categories": [
    "math.CO",
    "cs.DM",
    "cs.IT",
    "math.IT"
  ],
  "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 bound by Chv\\'atal. The main tool is the M\\\"obius function of a certain partially ordered set on $\\mathbb{N}$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-12-07T17:09:57.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C12",
      "05C76",
      "06A07"
    ],
    "keywords": [
      "metric dimension",
      "cartesian powers",
      "nonzero common difference",
      "distance matrix",
      "main tool"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 12,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}