Extremal Graph Theory for Metric Dimension and Diameter

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}_{β,D}$ be the set of graphs with metric dimension $β$ and diameter $D$. It is well-known that the minimum order of a graph in $\mathcal{G}_{β,D}$ is exactly $β+D$. The first contribution of this paper is to characterise the graphs in $\mathcal{G}_{β,D}$ with order $β+D$ for all values of $β$ and $D$. Such a characterisation was previously only known for $D\leq2$ or $β\leq1$. The second contribution is to determine the maximum order of a graph in $\mathcal{G}_{β,D}$ for all values of $D$ and $β$. Only a weak upper bound was previously known.

No reviews yet.

No comments yet.