{
  "id": "1203.1584",
  "version": "v2",
  "published": "2012-03-07T19:48:21.000Z",
  "updated": "2012-03-10T15:39:23.000Z",
  "title": "Extremal Graph Theory for Metric Dimension and Girth",
  "authors": [
    "Mohsen Jannesari"
  ],
  "comment": "6 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "A set $W\\subseteq V(G)$ is called a resolving set for $G$, if for each two distinct vertices $u,v\\in V(G)$ there exists $w\\in W$ such that $d(u,w)\\neq d(v,w)$, where $d(x,y)$ is the distance between the vertices $x$ and $y$. The minimum cardinality of a resolving set for $G$ is called the metric dimension of $G$, and denoted by $\\beta(G)$. In this paper, it is proved that in a connected graph $G$ of order $n$ which has a cycle, $\\beta(G)\\leq n-g(G)+2$, where $g(G)$ is the length of a shortest cycle in $G$, and the equality holds if and only if $G$ is a cycle, a complete graph or a complete bipartite graph $K_{s,t}$, $ s,t\\geq 2$.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2012-03-10T15:39:23.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "extremal graph theory",
      "metric dimension",
      "resolving set",
      "complete bipartite graph",
      "complete graph"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 6,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2012arXiv1203.1584J"
    }
  }
}