Extremal Graph Theory for Metric Dimension and Diameter

Abstract

A set of vertices $S$ \emph{resolves} a connected graph $G$ if every vertex is uniquely determined by its vector of distances to the vertices in $S$. The \emph{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\le 2$ or $\beta \le 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.