\magnification=1200
\hsize=4in
\overfullrule=0pt
\input amssym
%\def\frac#1 #2 {{#1\over #2}}
\def\emph#1{{\it #1}}
\def\em{\it}
\nopagenumbers
\noindent
%
%
{\bf Carmen Hernando, Merc{\`e} Mora, Ignacio M. Pelayo, Carlos Seara and David R. Wood}
%
%
\medskip
\noindent
%
%
{\bf Extremal Graph Theory for Metric Dimension and Diameter}
%
%
\vskip 5mm
\noindent
%
%
%
%
A set of vertices $S$ {\it resolves} a connected graph $G$ if every
vertex is uniquely determined by its vector of distances to the
vertices in $S$. The {\it metric dimension} of $G$ is the minimum
cardinality of a resolving set of $G$. Let ${\cal 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
${\cal G}_{\beta,D}$ is exactly $\beta+D$. The first contribution
of this paper is to characterise the graphs in ${\cal G}_{\beta,D}$
with order $\beta+D$ for all values of $\beta$ and $D$. Such a
characterisation was previously only known for $D\leq2$ or
$\beta\leq1$. The second contribution is to determine the maximum
order of a graph in ${\cal G}_{\beta,D}$ for all values of $D$ and
$\beta$. Only a weak upper bound was previously known.

\bye