On Reconstruction of Graphs From the Multiset of Subgraphs Obtained by Deleting ℓ Vertices
Alexandr V. Kostochka, Douglas B. West · IEEE Transactions on Information Theory · 2020
The Reconstruction Conjecture of Ulam asserts that, for n ≥ 3, every n-vertex graph is determined by the multiset of its induced subgraphs with n-1 vertices. The conjecture is known to hold for various special classes of graphs but remains wide open. We survey results on the more general conjecture by Kelly from 1957 that for every positive integerlthere exists Ml(with M1=3) such that when n ≥ Mlevery n-vertex graph is determined by the multiset of its induced subgraphs with n-lvertices.