تقرير
Degree lists and connectedness are $3$-reconstructible for graphs with at least seven vertices
| العنوان: | Degree lists and connectedness are $3$-reconstructible for graphs with at least seven vertices |
|---|---|
| المؤلفون: | Kostochka, Alexandr V., Nahvi, Mina, West, Douglas B., Zirlin, Dara |
| سنة النشر: | 2019 |
| المجموعة: | Mathematics |
| مصطلحات موضوعية: | Mathematics - Combinatorics |
| الوصف: | The $k$-deck of a graph is the multiset of its subgraphs induced by $k$ vertices. A graph or graph property is $l$-reconstructible if it is determined by the deck of subgraphs obtained by deleting $l$ vertices. We show that the degree list of an $n$-vertex graph is $3$-reconstructible when $n\ge7$, and the threshold on $n$ is sharp. Using this result, we show that when $n\ge7$ the $(n-3)$-deck also determines whether an $n$-vertex graph is connected; this is also sharp. These results extend the results of Chernyak and Manvel, respectively, that the degree list and connectedness are $2$-reconstructible when $n\ge6$, which are also sharp. Comment: 12 pages |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/1904.11901 |
| رقم الأكسشن: | edsarx.1904.11901 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |