A conjecture on the reconstruction of graphs from metric balls of their vertices

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⩾2r⩾2) around all its vertices. A metric ball of radius r   about vertex vv is the set of all vertices of distance at most r   from vv. The value t(r)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+22r+2 vertices shows that t(r)⩾2r+3t(r)⩾2r+3. We conjecture that t(r)=2r+3t(r)=2r+3. The main result is the upper bound t(r)⩽2r+2⌈(r-1)/4⌉+1t(r)⩽2r+2⌈(r-1)/4⌉+1 which, in particular, implies that this conjecture is true for r=2,3,4,5r=2,3,4,5. Moreover, it is proved that t(r)=2r+3t(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+32r+3 allows one to determine at least one edge of G.