Mathematics – Combinatorics
Scientific paper
2007-05-07
Mathematics
Combinatorics
Scientific paper
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\leq2$ or $\beta\leq1$. 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.
Hernando Carmen
Mora Merce
Pelayo Ignacio M.
Seara Carlos
Wood David R.
No associations
LandOfFree
Extremal Graph Theory for Metric Dimension and Diameter does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Extremal Graph Theory for Metric Dimension and Diameter, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Extremal Graph Theory for Metric Dimension and Diameter will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-598784