Hernando, Carmen; Mora, Mercè; Pelayo, Ignacio M.; Seara, Carlos; Wood, David R. Extremal graph theory for metric dimension and diameter. (English) Zbl 1219.05051 Electron. J. Comb. 17, No. 1, Research Paper R30, 28 p. (2010). 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. Cited in 68 Documents MSC: 05C12 Distance in graphs 05C35 Extremal problems in graph theory Keywords:graph; distance; resolving set; metric dimension; metric basis; diameter; order PDFBibTeX XMLCite \textit{C. Hernando} et al., Electron. J. Comb. 17, No. 1, Research Paper R30, 28 p. (2010; Zbl 1219.05051) Full Text: arXiv EuDML EMIS