{
  "id": "1704.04066",
  "version": "v1",
  "published": "2017-04-13T10:54:27.000Z",
  "updated": "2017-04-13T10:54:27.000Z",
  "title": "Bounds on metric dimension for families of planar graphs",
  "authors": [
    "Carl Joshua Quines",
    "Michael Sun"
  ],
  "comment": "6 pages. Comments welcomed",
  "categories": [
    "math.CO"
  ],
  "abstract": "The concept of metric dimension has applications in a variety of fields, such as chemistry, robotic navigation, and combinatorial optimization. We show bounds for graphs with $n$ vertices and metric dimension $\\beta$. For Hamiltonian outerplanar graphs, we have $\\beta \\leq \\left\\lceil\\frac{n}2\\right\\rceil$; for outerplanar graphs in general, we have $\\beta \\leq \\left\\lfloor\\frac{2n}{3}\\right\\rfloor$; for maximal planar graphs, we have $\\beta \\leq \\left\\lfloor\\frac{3n}{4}\\right\\rfloor$. We also show that bipyramids have a metric dimension of $\\left\\lfloor\\frac{2n}{5}\\right\\rfloor + 1$. It is conjectured that the metric dimension of maximal planar graphs in general is on the order of $\\left\\lfloor\\frac{2n}{5}\\right\\rfloor$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-04-13T10:54:27.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C10",
      "05C12"
    ],
    "keywords": [
      "metric dimension",
      "maximal planar graphs",
      "hamiltonian outerplanar graphs",
      "robotic navigation",
      "combinatorial optimization"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 6,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}