On reconstruction of graphs from the multiset of subgraphs obtained by deleting $\ell$ vertices

التفاصيل البيبلوغرافية
العنوان: On reconstruction of graphs from the multiset of subgraphs obtained by deleting $\ell$ vertices
المؤلفون: Kostochka, Alexandr V., West, Douglas B.
سنة النشر: 2020
المجموعة: Mathematics
مصطلحات موضوعية: Mathematics - Combinatorics, 05C60, 05C07
الوصف: The Reconstruction Conjecture of Ulam asserts that, for $n\geq 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 $\ell$ there exists $M_\ell$ (with $M_1=3$) such that when $n\geq M_\ell$ every $n$-vertex graph is determined by the multiset of its induced subgraphs with $n-\ell$ vertices.
نوع الوثيقة: Working Paper
URL الوصول: http://arxiv.org/abs/2004.05527
رقم الأكسشن: edsarx.2004.05527
قاعدة البيانات: arXiv