The simultaneous metric dimension of graph families

Let G=(V,E) be a connected graph. A vertex v∈V is said to resolve two vertices x and y if dG(v,x)≠dG(v,y). A set S⊆V is said to be a metric generator for G if any pair of vertices of G is resolved by some element of S. A minimum cardinality metric generator is called a metric basis, and its cardinality, dim(G), the metric dimension of G. A set S⊆V is said to be a simultaneous metric generator for a graph family G={G1,G2,…,Gk}, defined on a common (labeled) vertex set, if it is a metric generator for every graph of the family. A minimum cardinality simultaneous metric generator is called a simultaneous metric basis, and its cardinality the simultaneous metric dimension of G. We obtain sharp bounds for these invariants for general families of graphs and calculate closed formulae or tight bounds for the simultaneous metric dimension of several specific graph families. For a given graph G we describe a process for obtaining a lower bound on the maximum number of graphs in a family containing G that has simultaneous metric dimension equal to dim(G). It is shown that the problem of finding the simultaneous metric dimension of families of trees is NP-hard. Sharp upper bounds for the simultaneous metric dimension of trees are established. The problem of finding this invariant for families of trees that can be obtained from an initial tree by a sequence of successive edge-exchanges is considered. For such families of trees sharp upper and lower bounds for the simultaneous metric dimension are established.