A conjecture on the reconstruction of graphs from metric balls of their vertices
A conjecture on the reconstruction of graphs from metric balls of their vertices
复制标题
关于从顶点的度量球重构图的猜想
DOI：
10.1016/j.disc.2007.09.027
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
V. Levenshtein
中科院分区：
文献类型：
--
作者：
V. Levenshtein
本文研究了Levenshtein，Konstantinova，Konstantinov和Molodtsov在一篇论文中提出的一个新的图重构问题。数学，接受出版]，以化合物的重建为动机。它由一个未知的简单连通图G的所有顶点周围半径为r(r⩾2)的度量球的顶点子集精确重构而成。关于顶点v的半径为r的度量球是距离v至多为r的所有顶点的集合，引入了等于最小数t的值t(R)，使得一个没有末端顶点且围长至少为t的简单连通图G可以由围绕其所有顶点的半径为r的度量球重构.对2r+2点圈图的讨论表明t(R)⩾2r+3.我们猜想t(R)=2r+3.主要结果是上界t(R)⩽2r+2⌈(r-1)/4⌉+1.特别是当r=2，3，4，5时，这一猜想成立.此外，如果一个无围长至少为2r+3的简单连通图的所有顶点周围半径为r的度量球的知识允许一个人确定G的至少一条边，则t(R)=2r+3.
In this paper we investigate a new graph reconstruction problem which was introduced in a paper by Levenshtein, Konstantinova, Konstantinov and Molodtsov [Reconstruction of a graph from 2-vicinities of its vertices, Discrete Appl. Math., accepted for publication], motivated by reconstruction of chemical compounds. It consists of the exact reconstruction of an unknown simple connected graph G from subsets of vertices which are metric balls of radius r (r⩾2) around all its vertices. A metric ball of radius r about vertex v is the set of all vertices of distance at most r from v. The value t(r) is introduced which is equal to the minimum number t such that a simple connected graph G without terminal vertices with girth at least t is reconstructible from metric balls of radius r around all its vertices. Consideration of the cycle graph with 2r+2 vertices shows that t(r)⩾2r+3. We conjecture that t(r)=2r+3. The main result is the upper bound t(r)⩽2r+2⌈(r-1)/4⌉+1 which, in particular, implies that this conjecture is true for r=2,3,4,5. Moreover, it is proved that t(r)=2r+3 if the knowledge of metric balls of radius r around all vertices of a simple connected graph G without terminal vertices with girth at least 2r+3 allows one to determine at least one edge of G.