On Local Metric Dimensions of Graphs

Abstract

For an ordered set $W=\{w_1,w_2,\dots ,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
$$\text{code}(v)=(d(v,w_1),d(v,w_2),\dots ,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 $\text{code}(u)\ne \text{code}(v)$ for every pair $u,v$ of adjacent vertices of $G$. The minimum positive integer $k$ for which $G$ has a local metric set of cardinality $k$ is the local metric dimension $\text{lmd}(G)$ of $G$. We determine the local metric dimensions of joins and compositions of some well-known classes of graphs, namely complete graphs, cycles, and paths. For a nontrivial connected graph $G$, a vertex $v$ of $G$, and an edge $e$ of $G$, where $v$ is not a cut-vertex and $e$ is not a bridge, it is shown that $\text{lmd}(G–v)\le \text{lmd}(G)+\text{deg}(v)$ and $\text{lmd}(G–e)\le \text{lmd}(G)+2.$ The sharpness of these two bounds is studied. We also present several open questions in this area of research.