Acyclic graphs with at least $2\ell+1$ vertices are $\ell$-recognizable

التفاصيل البيبلوغرافية
العنوان: Acyclic graphs with at least $2\ell+1$ vertices are $\ell$-recognizable
المؤلفون: Kostochka, Alexandr V., Nahvi, Mina, West, Douglas B., Zirlin, Dara
سنة النشر: 2023
المجموعة: Mathematics
مصطلحات موضوعية: Mathematics - Combinatorics
الوصف: The $(n-\ell)$-deck of an $n$-vertex graph is the multiset of subgraphs obtained from it by deleting $\ell$ vertices. A family of $n$-vertex graphs is $\ell$-recognizable if every graph having the same $(n-\ell)$-deck as a graph in the family is also in the family. We prove that the family of $n$-vertex graphs with no cycles is $\ell$-recognizable when $n\ge2\ell+1$ (except for $(n,\ell)=(5,2)$). As a consequence, the family of $n$-vertex trees is $\ell$-recognizable when $n\ge2\ell+1$ and $\ell\ne2$. It is known that this fails when $n=2\ell$.
نوع الوثيقة: Working Paper
URL الوصول: http://arxiv.org/abs/2308.04509
رقم الأكسشن: edsarx.2308.04509
قاعدة البيانات: arXiv