{
  "id": "1410.7287",
  "version": "v1",
  "published": "2014-10-27T16:05:26.000Z",
  "updated": "2014-10-27T16:05:26.000Z",
  "title": "The $k$-metric dimension of the lexicographic product of graphs",
  "authors": [
    "A. Estrada-Moreno",
    "I. G. Yero",
    "J. A. Rodríguez-Velázquez"
  ],
  "comment": "18 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "Given a simple and connected graph $G=(V,E)$, and a positive integer $k$, a set $S\\subseteq V$ is said to be a $k$-metric generator for $G$, if for any pair of different vertices $u,v\\in V$, there exist at least $k$ vertices $w_1,w_2,...,w_k\\in S$ such that $d_G(u,w_i)\\ne d_G(v,w_i)$, for every $i\\in \\{1,...,k\\}$, where $d_G(x,y)$ denotes the distance between $x$ and $y$. The minimum cardinality of a $k$-metric generator is the $k$-metric dimension of $G$. A set $S\\subseteq V$ is a $k$-adjacency generator for $G$ if any two different vertices $x,y\\in V(G)$ satisfy $|((N_G(x)\\triangledown N_G(y))\\cup\\{x,y\\})\\cap S|\\ge k$, where $N_G(x)\\triangledown N_G(y)$ is the symmetric difference of the neighborhoods of $x$ and $y$. The minimum cardinality of any $k$-adjacency generator is the $k$-adjacency dimension of $G$. In this article we obtain tight bounds and closed formulae for the $k$-metric dimension of the lexicographic product of graphs in terms of the $k$-adjacency dimension of the factor graphs.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2014-10-27T16:05:26.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C12",
      "05C76"
    ],
    "keywords": [
      "metric dimension",
      "lexicographic product",
      "adjacency generator",
      "minimum cardinality",
      "adjacency dimension"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 18,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2014arXiv1410.7287E"
    }
  }
}