Extremal Graph Theory for Metric Dimension and Diameter
Extremal Graph Theory for Metric Dimension and Diameter
复制标题
DOI：
10.37236/302
复制
发表时间：
2007-05
期刊：
影响因子：
--
通讯作者：
C. Hernando;M. Mora;I. Pelayo;C. Seara;D. Wood
中科院分区：
文献类型：
--
作者：
C. Hernando;M. Mora;I. Pelayo;C. Seara;D. Wood
一个顶点集$S$分解一个连通图$G$，如果每个顶点都由它到$S$中顶点的距离向量唯一确定。$G$的度量维数是$G$的分解集的最小基数。设${\cal G}_{\beta，D}$是度量维数为$\beta$，直径为$D$的图的集合。众所周知，${\cal G}_{\beta，D}$中的图的最小阶恰好是$\beta+D$。本文的第一个贡献是对${\calG}_{\beta，D}$中的阶为$\beta+D$的图进行了全图化。这种特性以前只知道为$D\leq2$或$\beta\leq1$。第二个贡献是确定${\cal G}_{\beta，D}$中一个图的最大阶，对于$D$和$\beta$的所有值。以前只知道一个弱上界。
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.