{
  "id": "0705.0938",
  "version": "v1",
  "published": "2007-05-07T16:16:12.000Z",
  "updated": "2007-05-07T16:16:12.000Z",
  "title": "Extremal Graph Theory for Metric Dimension and Diameter",
  "authors": [
    "Carmen Hernando",
    "Merce Mora",
    "Ignacio M. Pelayo",
    "Carlos Seara",
    "David R. Wood"
  ],
  "journal": "Electronic J. Combinatorics 17.1:R30, 2010",
  "categories": [
    "math.CO"
  ],
  "abstract": "A set of vertices $S$ \\emph{resolves} a connected graph $G$ if every vertex is uniquely determined by its vector of distances to the vertices in $S$. The \\emph{metric dimension} of $G$ is the minimum cardinality of a resolving set of $G$. Let $\\mathcal{G}_{\\beta,D}$ be the set of graphs with metric dimension $\\beta$ and diameter $D$. It is well-known that the minimum order of a graph in $\\mathcal{G}_{\\beta,D}$ is exactly $\\beta+D$. The first contribution of this paper is to characterise the graphs in $\\mathcal{G}_{\\beta,D}$ with order $\\beta+D$ for all values of $\\beta$ and $D$. Such a characterisation was previously only known for $D\\leq2$ or $\\beta\\leq1$. The second contribution is to determine the maximum order of a graph in $\\mathcal{G}_{\\beta,D}$ for all values of $D$ and $\\beta$. Only a weak upper bound was previously known.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2007-05-07T16:16:12.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C12",
      "05C35"
    ],
    "keywords": [
      "extremal graph theory",
      "metric dimension",
      "weak upper bound",
      "minimum order",
      "first contribution"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2007arXiv0705.0938H"
    }
  }
}