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

This very nice paper investigates an interesting variant of the graph reconstruction theme. Let \(G\) be a labelled graph. For any vertex \(v\) in \(G\), the ball \(B_r(v)\) for \(r\geq 2\) is the set of vertices at distance at most \(r\) from \(v\) with \(v\) itself indicated as the centre of the ball. The question is to reconstruct \(G\) identically from the balls \(B_r(V)\) for all \(v\) in \(G\). The author considers the number \(t(r)\) which is equal to the minimum number \(t\) such that a simple connected graph without terminal vertices and with girth at least \(t\) is reconstructible from the balls \(B_r(v)\). Consideration of the cycle with \(2r+2\) vertices shows that \(t(r)\geq 2r+3\). The author conjectures that, in fact, \(t(r)=2r+3\). The main result of the paper is the upper bound \(t(r)\leq 2r+2\lceil (r-1)/4 \rceil +1\) which, in particular, implies the conjecture for \(r=2,3,4,5\). It is also proved that \(t(r)=2r+3\) if \(G\) has no terminal vertices and apart from the balls \(B_r(v)\) one knows at least one edge of \(G\).