Extremal Graph Theory for Metric Dimension and Diameter

A set of vertices S resolves a connected graph G if every vertex is uniquely determined by its vector of distances to the vertices in S. The metric dimension of G is the minimum cardinality of a resolving set of G. Let Gβ,D be the set of graphs with metric dimension β and diameter D. It is well-known that the minimum order of a graph in Gβ,D is exactly β+D. The first contribution of this paper is to characterise the graphs in Gβ,D with order β+D for all values of β and D. Such a characterisation was previously only known for D≤2 or β≤1. The second contribution is to determine the maximum order of a graph in Gβ,D for all values of D and β. Only a weak upper bound was previously known.