TY - JOUR
T1 - On Reconstruction of Graphs from the Multiset of Subgraphs Obtained by Deleting ℓ Vertices
AU - Kostochka, Alexandr V.
AU - West, Douglas B.
N1 - Manuscript received August 29, 2019; revised February 2, 2020; accepted March 9, 2020. Date of publication March 27, 2020; date of current version May 20, 2021. This work was supported in part by the NSF under Grant DMS-1600592 and in part by the Russian Foundation for Basic Research under Grant 18-01-00353A and Grant 19-01-00682. The work of Douglas B. West was supported by the National Natural Science Foundation of China under NNSFC Grant 11871439 and Grant 11971439. (Corresponding author: Douglas B. West.) Alexandr V. Kostochka was with the Sobolev Institute of Mathematics, 630090 Novosibirsk, Russia. He is now with the Department of Mathematics, University of Illinois at Urbana–Champaign, Urbana, IL 61801 USA (e-mail: [email protected]).
PY - 2021/6
Y1 - 2021/6
N2 - 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 integer ℓ there exists M ℓ (with M1=3 ) such that when n ≥ M ℓ every n -vertex graph is determined by the multiset of its induced subgraphs with n-ℓ vertices.
AB - 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 integer ℓ there exists M ℓ (with M1=3 ) such that when n ≥ M ℓ every n -vertex graph is determined by the multiset of its induced subgraphs with n-ℓ vertices.
KW - Graph reconstruction
KW - connected
KW - deck
KW - random graph
KW - reconstructibility
UR - http://www.scopus.com/inward/record.url?scp=85103810061&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85103810061&partnerID=8YFLogxK
U2 - 10.1109/TIT.2020.2983678
DO - 10.1109/TIT.2020.2983678
M3 - Article
AN - SCOPUS:85103810061
SN - 0018-9448
VL - 67
SP - 3278
EP - 3286
JO - IEEE Transactions on Information Theory
JF - IEEE Transactions on Information Theory
IS - 6
M1 - 9049107
ER -