Sách Extremal Graph Theory for Metric Dimension and Diameter

Abstract
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 6 2 or β 6 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.