{
  "id": "1010.4495",
  "version": "v3",
  "published": "2010-10-21T15:25:32.000Z",
  "updated": "2011-11-24T21:50:42.000Z",
  "title": "On the metric dimension of Grassmann graphs",
  "authors": [
    "Robert F. Bailey",
    "Karen Meagher"
  ],
  "comment": "9 pages. Revised to correct an error in Proposition 9 of the previous version",
  "categories": [
    "math.CO"
  ],
  "abstract": "The {\\em metric dimension} of a graph $\\Gamma$ is the least number of vertices in a set with the property that the list of distances from any vertex to those in the set uniquely identifies that vertex. We consider the Grassmann graph $G_q(n,k)$ (whose vertices are the $k$-subspaces of $\\mathbb{F}_q^n$, and are adjacent if they intersect in a $(k-1)$-subspace) for $k\\geq 2$, and find a constructive upper bound on its metric dimension. Our bound is equal to the number of 1-dimensional subspaces of $\\mathbb{F}_q^n$.",
  "revisions": [
    {
      "version": "v3",
      "updated": "2011-11-24T21:50:42.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C12",
      "05E30"
    ],
    "keywords": [
      "metric dimension",
      "grassmann graph",
      "constructive upper bound",
      "set uniquely identifies"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 9,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2010arXiv1010.4495B"
    }
  }
}