Extremal graph theory for metric dimension and diameter

Carmen Hernando ; Mercè Mora ; Ignacio M. Pelayo ; Carlos Seara ; David R. Wood

The electronic journal of combinatorics, Tome 17 (2010)

Résumé

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 ${\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.

Détail

DOI : 10.37236/302

Classification : 05C12, 05C35
Mots-clés : graph, distance, resolving set, metric dimension, metric basis, diameter, order