Reconstruction of a graph from 2-vicinities of its vertices
Reconstruction of a graph from 2-vicinities of its vertices
复制标题
从图的顶点的 2 邻域重建图
DOI：
10.1016/j.dam.2006.11.016
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
S. Molodtsov
中科院分区：
文献类型：
--
作者：
V. Levenshtein;E. Konstantinova;E. Konstantinov;S. Molodtsov
我们证明了一个连通图的直径至少为4和围长7或更多（特别是树），可以完全重建的度量球半径为2的所有顶点。另一方面，存在直径为3和围长为6的图，它们是不可重构的。这个新的图论问题的动机是重建的化合物。
We prove that a connected graph of diameter at least 4 and of girth 7 or more (in particular, a tree) can be exactly reconstructed from metric balls of radius 2 of all its vertices. On the other hand, there exist graphs of diameter 3 and of girth 6 which are not reconstructible. This new graph theory problem is motivated by reconstruction of chemical compounds.