The local metric dimension of a graph
Futaba Okamoto, Bryan Phinezy, Ping Zhang · Mathematica Bohemica · 2010
For an ordered set $W= \{w_1,w_2,\ldots ,w_k\}$ of $k$ distinct vertices in a nontrivial connected graph $G$, the metric code of a vertex $v$ of $G$ with respect to $W$ is the $k$-vector \[ \mathop {\rm code}(v)= ( d(v,w_1),d(v,w_2),\cdots ,d(v,w_k) ) \] where $d(v,w_i)$ is the distance between $v$ and $w_i$ for $1\le i\le k$. The set $W$ is a local metric set of $G$ if $\mathop {\rm code}(u) e \mathop {\rm code}(v)$ for every pair $u,v$ of adjacent vertices of $G$. The minimum positive integer $k$ for which $G$ has a local metric $k$-set is the local metric dimension $\mathop {\rm lmd}(G)$ of $G$. A local metric set of $G$ of cardinality $\mathop {\rm lmd}(G)$ is a local metric basis of $G$. We characterize all nontrivial connected graphs of order $n$ having local metric dimension $1$, $n-2$, or $n-1$ and establish sharp bounds for the local metric dimension of a graph in terms of well-known graphical parameters. Several realization results are presented along with other results on the number of local metric bases of a connected graph.