zbMATH — the first resource for mathematics

Extremal graph theory for metric dimension and diameter. (English) Zbl 1219.05051
Summary: 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 \({\mathcal G}_{\beta,D}\) be the set of graphs with metric dimension \(\beta\) and diameter \(D\). It is well-known that the minimum order of a graph in \({\mathcal G}_{\beta,D}\) is exactly \(\beta+ D\).
The first contribution of this paper is to characterise the graphs in \({\mathcal G}_{\beta,D}\) with order \(\beta+ D\) for all values of \(\beta\) and \(D\). Such a characterisation was previously only known for \(D\leq 2\) or \(\beta\leq 1\).
The second contribution is to determine the maximum order of a graph in \({\mathcal G}_{\beta,D}\) for all values of \(D\) and \(\beta\). Only a weak upper bound was previously known.

05C12 Distance in graphs
05C35 Extremal problems in graph theory
Full Text: EuDML EMIS