Computing the local metric dimension of a graph from the local metric dimension of primary subgraphs

Abstract

For an ordered subset W= w₁, w₂, … w_k of vertices and a vertex u in a connected graph G, the representation of u with respect to W is the ordered k-tuple r(u|W)=(d(u, w₁), d(u, w₂), … , d(u, w_k)), where d(x, y) represents the distance between the vertices x and y. The set W is a local metric generator for G if every two adjacent vertices of G have distinct representations. A minimum local metric generator is called a local metric basis for G and its cardinality the local metric dimension of G. We show that the computation of the local metric dimension of a graph with cut vertices is reduced to the computation of the local metric dimension of the so-called primary subgraphs. The main results are applied to specific constructions including bouquets of graphs, rooted product graphs, corona product graphs, block graphs and chain of graphs.

Keywords:

• local metric dimension
• rooted product graphs
• corona graphs
• metric dimension
• primary subgraphs

2010 AMS Subject Classifications::

• 05C12
• 05C76
• 05C69