标题： 并非每个图都可以从其边界距离矩阵重构出来 显示英文标题

标题： Not every graph can be reconstructed from its boundary distance matrix

摘要： 如果对于连通图 $G$ 中的某个其他顶点 $u$，没有任何一个顶点 $v$ 的邻居与 $u$ 的距离比 $v$ 更远，则称该顶点 $v$ 为 $G$ 的边界顶点。 边界$\partial(G)$的$G$是其所有边界顶点的集合。 图 $G=([n],E)$ 的边界距离矩阵 $\hat{D}_G$ 是 $\kappa$ 阶方阵，其中 $\kappa$ 是 $\partial(G)$ 的阶，并且对于每个 $i,j\in \partial(G)$，$[\hat{D}_G]_{ij}=d_G(i,j)$。 在最近的一篇论文 [doi.org/10.7151/dmgt.2567] 中证明了，若图$G$要么是块图要么是单圈图，则$G$可由$G$的边界距离矩阵$\hat{D}_{G}$唯一确定，并且还推测该命题对于每个连通图$G$都成立，只要$G$的阶数$n$和边界（从而也包括边界距离矩阵）都事先固定。 在证明了该猜想对于直径为 2 的图类、阶数最多为$n=6$的图类或 Ptolemaic 图类成立之后，我们表明当考虑例如直径为 3 且阶数至少为$n=10$的分裂图族或者阶数至少为$n=8$的距离保持图族时，该命题不成立。 显示英文摘要

摘要： A vertex $v$ of a connected graph $G$ is said to be a boundary vertex of $G$ if for some other vertex $u$ of $G$, no neighbor of $v$ is further away from $u$ than $v$. The boundary $\partial(G)$ of $G$ is the set of all of its boundary vertices. The boundary distance matrix $\hat{D}_G$ of a graph $G=([n],E)$ is the square matrix of order $\kappa$, being $\kappa$ the order of $\partial(G)$, such that for every $i,j\in \partial(G)$, $[\hat{D}_G]_{ij}=d_G(i,j)$. In a recent paper [doi.org/10.7151/dmgt.2567], it was shown that if a graph $G$ is either a block graph or a unicyclic graph, then $G$ is uniquely determined by the boundary distance matrix $\hat{D}_{G}$ of $G$, and it was also conjectured that this statement holds for every connected graph $G$, whenever both the order $n$ and the boundary (and thus also the boundary distance matrix) of $G$ are prefixed. After proving that this conjecture is true for several graph families, such as being of diameter 2, having order at most $n=6$ or being Ptolemaic, we show that this statement does not hold when considering, for example, either the family of split graphs of diameter 3 and order at least $n=10$ or the family of distance-hereditary graphs of order at least $n=8$.