{
  "id": "1305.0363",
  "version": "v1",
  "published": "2013-05-02T08:00:26.000Z",
  "updated": "2013-05-02T08:00:26.000Z",
  "title": "The metric dimension of strong product graphs",
  "authors": [
    "Juan A. Rodriguez-Velazquez",
    "Dorota Kuziak",
    "Ismael G. Yero",
    "Jose M. Sigarreta"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "For an ordered subset $S = \\{s_1, s_2,\\dots s_k\\}$ of vertices and a vertex $u$ in a connected graph $G$, the metric representation of $u$ with respect to $S$ is the ordered $k$-tuple $ r(u|S)=(d_G(v,s_1), d_G(v,s_2),\\dots,$ $d_G(v,s_k))$, where $d_G(x,y)$ represents the distance between the vertices $x$ and $y$. The set $S$ is a metric generator for $G$ if every two different vertices of $G$ have distinct metric representations. A minimum metric generator is called a metric basis for $G$ and its cardinality, $dim(G)$, the metric dimension of $G$. It is well known that the problem of finding the metric dimension of a graph is NP-Hard. In this paper we obtain closed formulae and tight bounds for the metric dimension of strong product graphs.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2013-05-02T08:00:26.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C12",
      "05C38",
      "05C69",
      "05C76"
    ],
    "keywords": [
      "strong product graphs",
      "metric dimension",
      "distinct metric representations",
      "minimum metric generator",
      "tight bounds"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2013arXiv1305.0363R"
    }
  }
}