zbMATH — the first resource for mathematics

The local metric dimension of a graph. (English) Zbl 1224.05152
Summary: 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 \( \operatorname {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\leq i\leq k\). The set \(W\) is a local metric set of \(G\) if \(\operatorname {code}(u)\neq \operatorname {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 \(\operatorname {lmd}(G)\) of \(G\). A local metric set of \(G\) of cardinality \(\operatorname {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.

05C12 Distance in graphs
05C40 Connectivity
Full Text: EMIS EuDML