On Minimum Girth of Graphs Reconstructible from Metric Balls of Their Vertices

Traditional problems of coding theory consist of finding, for a given graph (in particular, for the Hamming and Johnson graphs), a maximum subset of vertices whose metric balls of a given radius do not intersect and a minimum subset of vertices whose metric balls of a given radius cover all vertices of the graph. In the paper another problem formulated in terms of metric balls of vertices is considered. We investigate conditions under which an unknown graph can be uniquely reconstructible if metric balls of a given radius around each vertex are known