کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4655042 | 1632928 | 2016 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
High girth augmented trees are huge
ترجمه فارسی عنوان
درختان تکثیر شده زیاد، بزرگ هستند
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
Let G be a graph consisting of a complete binary tree of depth h together with one back edge leading from each leaf to one of its ancestors, and suppose that the girth of G exceeds g . Let h=h(g)h=h(g) be the minimum possible depth of such a graph. The existence of such graphs, for arbitrarily large g, is proved in [2], where it is shown that h(g)h(g) is at most some version of the Ackermann function. Here we show that this is tight and the growth of h(g)h(g) is indeed Ackermannian.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series A - Volume 144, November 2016, Pages 7–15
Journal: Journal of Combinatorial Theory, Series A - Volume 144, November 2016, Pages 7–15
نویسندگان
Noga Alon,