Extremal graph theory for metric dimension and diameter (Q2380462): Difference between revisions

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.