{
  "id": "1312.4971",
  "version": "v3",
  "published": "2013-12-17T21:02:36.000Z",
  "updated": "2014-09-17T20:29:22.000Z",
  "title": "On the metric dimension of imprimitive distance-regular graphs",
  "authors": [
    "Robert F. Bailey"
  ],
  "comment": "17 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "A resolving set for a graph $\\Gamma$ is a collection of vertices $S$, chosen so that for each vertex $v$, the list of distances from $v$ to the members of $S$ uniquely specifies $v$. The metric dimension of $\\Gamma$ is the smallest size of a resolving set for $\\Gamma$. Much attention has been paid to the metric dimension of distance-regular graphs. Work of Babai from the early 1980s yields general bounds on the metric dimension of primitive distance-regular graphs in terms of their parameters. In this paper, by considering three families of imprimitive distance-regular graphs (bipartite doubles, Taylor graphs, and the incidence graphs of symmetric designs), we show that this holds for some infinite families of imprimitive graphs, and fails for some others.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2014-01-13T18:44:40.000Z",
      "abstract": "A {\\em resolving set} for a graph $\\Gamma$ is a collection of vertices $S$, chosen so that for each vertex $v$, the list of distances from $v$ to the members of $S$ uniquely specifies $v$. The {\\em metric dimension} of $\\Gamma$ is the smallest size of a resolving set for $\\Gamma$. Much attention has been paid to the metric dimension of distance-regular graphs. In this paper, we consider the metric dimension of three families of imprimitive distance-regular graphs: bipartite doubles, Taylor graphs, and the incidence graphs of symmetric designs. In each case, we demonstrate a connection between the metric dimension of $\\Gamma$ to that of a related primitive graph.",
      "comment": "14 pages",
      "journal": null,
      "doi": null
    },
    {
      "version": "v3",
      "updated": "2014-09-17T20:29:22.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05E30",
      "05C12",
      "51E05"
    ],
    "keywords": [
      "metric dimension",
      "imprimitive distance-regular graphs",
      "resolving set",
      "bipartite doubles",
      "taylor graphs"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 17,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2013arXiv1312.4971B"
    }
  }
}