{
  "id": "1804.08147",
  "version": "v1",
  "published": "2018-04-22T18:05:56.000Z",
  "updated": "2018-04-22T18:05:56.000Z",
  "title": "The connected metric dimension at a vertex of a graph",
  "authors": [
    "Linda Eroh",
    "Cong X. Kang",
    "Eunjeong Yi"
  ],
  "comment": "23 pages, 12 figures",
  "categories": [
    "math.CO"
  ],
  "abstract": "The notion of metric dimension, $dim(G)$, of a graph $G$, as well as a number of variants, is now well studied. In this paper, we begin a local analysis of this notion by introducing $cdim_G(v)$, \\emph{the connected metric dimension of $G$ at a vertex $v$}, which is defined as follows: a set of vertices $S$ of $G$ is a \\emph{resolving set} if, for any pair of distinct vertices $x$ and $y$ of $G$, there is a vertex $z \\in S$ such that the distance between $z$ and $x$ is distinct from the distance between $z$ and $y$ in $G$. We call a resolving set $S$ \\emph{connected} if $S$ induces a connected subgraph of $G$. Then, $cdim_G(v)$ is defined to be the minimum of the cardinalities of all connected resolving sets which contain the vertex $v$. The \\emph{connected metric dimension of $G$}, denoted by $cdim(G)$, is $\\min\\{cdim_G(v): v \\in V(G)\\}$. Noting that $1 \\le dim(G) \\le cdim(G) \\le cdim_G(v) \\le |V(G)|-1$ for any vertex $v$ of $G$, we show the existence of a pair $(G,v)$ such that $cdim_G(v)$ takes all positive integer values from $dim(G)$ to $|V (G)|-1$, as $v$ varies in a fixed graph $G$. We characterize graphs $G$ and their vertices $v$ satisfying $cdim_G(v) \\in \\{1, |V(G)|-1\\}$. We show that $cdim(G)=2$ implies $G$ is planar, whereas it is well known that there is a non-planar graph $H$ with $dim(H)=2$. We also characterize trees and unicyclic graphs $G$ satisfying $cdim(G)=dim(G)$. We show that $cdim(G)-dim(G)$ can be arbitrarily large. We determine $cdim(G)$ and $cdim_G(v)$ for some classes of graphs. We further examine the effect of vertex or edge deletion on the connected metric dimension. We conclude with some open problems.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2018-04-22T18:05:56.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C12"
    ],
    "keywords": [
      "connected metric dimension",
      "resolving set",
      "distinct vertices",
      "local analysis",
      "open problems"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 23,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}