{
  "id": "1112.2326",
  "version": "v1",
  "published": "2011-12-11T07:12:44.000Z",
  "updated": "2011-12-11T07:12:44.000Z",
  "title": "Relations between Metric Dimension and Domination Number of Graphs",
  "authors": [
    "Behrooz Bagheri Gh.",
    "Mohsen Jannesari",
    "Behnaz Omoomi"
  ],
  "comment": "6 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "A set $W\\subseteq V(G)$ is called a resolving set, 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, we prove that in a connected graph $G$ of order $n$, $\\beta(G)\\leq n-\\gamma(G)$, where $\\gamma(G)$ is the domination number of $G$, and the equality holds if and only if $G$ is a complete graph or a complete bipartite graph $K_{s,t}$, $ s,t\\geq 2$. Then, we obtain new bounds for $\\beta(G)$ in terms of minimum and maximum degree of $G$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2011-12-11T07:12:44.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "domination number",
      "metric dimension",
      "resolving set",
      "complete bipartite graph",
      "minimum cardinality"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 6,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2011arXiv1112.2326B"
    }
  }
}