Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9514504 | Electronic Notes in Discrete Mathematics | 2005 | 5 Pages |
Abstract
We prove that a connected graph of diameter at least 4 and of girth 7 or more (in particular, a tree) can be exactly reconstructed from metric balls of radius 2 of all its vertices. On the other hand, there exist graphs of diameter 3 and of girth 6 which are not reconstructible. This new graph theory problem is motivated by reconstruction of chemical compounds.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Vladimir Levenshtein, Elena Konstantinova, Eugene Konstantinov, Sergey Molodtsov,