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

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 (image) around all its vertices. A metric ball of radius r about vertex image is the set of all vertices of distance at most r from image. The value image 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 image vertices shows that image. We conjecture that image. The main result is the upper bound image which, in particular, implies that this conjecture is true for image. Moreover, it is proved that image 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 image allows one to determine at least one edge of G.