{
  "id": "1107.4140",
  "version": "v1",
  "published": "2011-07-20T23:34:34.000Z",
  "updated": "2011-07-20T23:34:34.000Z",
  "title": "On the metric dimension of line graphs",
  "authors": [
    "Min Feng",
    "Min Xu",
    "Kaishun Wang"
  ],
  "comment": "7 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "Let $G$ be a (di)graph. A set $W$ of vertices in $G$ is a \\emph{resolving set} of $G$ if every vertex $u$ of $G$ is uniquely determined by its vector of distances to all the vertices in $W$. The \\emph{metric dimension} $\\mu (G)$ of $G$ is the minimum cardinality of all the resolving sets of $G$. C\\'aceres et al. \\cite{Ca2} computed the metric dimension of the line graphs of complete bipartite graphs. Recently, Bailey and Cameron \\cite{Ba} computed the metric dimension of the line graphs of complete graphs. In this paper we study the metric dimension of the line graph $L(G)$ of $G$. In particular, we show that $\\mu(L(G))=|E(G)|-|V(G)|$ for a strongly connected digraph $G$ except for directed cycles, where $V(G)$ is the vertex set and $E(G)$ is the edge set of $G$. As a corollary, the metric dimension of de Brujin digraphs and Kautz digraphs is given. Moreover, we prove that $\\lceil\\log_2\\Delta(G)\\rceil\\leq\\mu(L(G))\\leq |V(G)|-2$ for a simple connected graph $G$ with at least five vertices, where $\\Delta(G)$ is the maximum degree of $G$. Finally, we obtain the metric dimension of the line graph of a tree in terms of its parameters.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2011-07-20T23:34:34.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "metric dimension",
      "line graph",
      "complete bipartite graphs",
      "maximum degree",
      "complete graphs"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 7,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2011arXiv1107.4140F"
    }
  }
}