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 \leq i \leq k \). The set \( W \) is a local metric set of \( G \) if \( \text{code}(u) \neq \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) \leq \text{lmd}(G) + \text{deg}(v)
$$
and
$$
\text{lmd}(G – e) \leq \text{lmd}(G) + 2.
$$
The sharpness of these two bounds is studied. We also present several open questions in this area of research.