{
  "id": "1409.4510",
  "version": "v1",
  "published": "2014-09-16T05:25:14.000Z",
  "updated": "2014-09-16T05:25:14.000Z",
  "title": "Minimum Weight Resolving Sets of Grid Graphs",
  "authors": [
    "Patrick Andersen",
    "Cyriac Grigorious",
    "Mirka Miller"
  ],
  "comment": "21 pages, 10 figures",
  "categories": [
    "math.CO"
  ],
  "abstract": "For a simple graph $G=(V,E)$ and for a pair of vertices $u,v \\in V$, we say that a vertex $w \\in V$ resolves $u$ and $v$ if the shortest path from $w$ to $u$ is of a different length than the shortest path from $w$ to $v$. A set of vertices ${R \\subseteq V}$ is a resolving set if for every pair of vertices $u$ and $v$ in $G$, there exists a vertex $w \\in R$ that resolves $u$ and $v$. The minimum weight resolving set problem is to find a resolving set $M$ for a weighted graph $G$ such that$\\sum_{v \\in M} w(v)$ is minimum, where $w(v)$ is the weight of vertex $v$. In this paper, we explore the possible solutions of this problem for grid graphs $P_n \\square P_m$ where $3\\leq n \\leq m$. We give a complete characterisation of solutions whose cardinalities are 2 or 3, and show that the maximum cardinality of a solution is $2n-2$. We also provide a characterisation of a class of minimals whose cardinalities range from $4$ to $2n-2$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2014-09-16T05:25:14.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C12"
    ],
    "keywords": [
      "grid graphs",
      "shortest path",
      "minimum weight resolving set problem",
      "cardinality",
      "characterisation"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 21,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2014arXiv1409.4510A"
    }
  }
}