Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
419874 | Discrete Applied Mathematics | 2008 | 8 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
Computer Science
Computational Theory and Mathematics
Authors
Vladimir Levenshtein, Elena Konstantinova, Eugene Konstantinov, Sergey Molodtsov,