کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
8903572 | 1632746 | 2018 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the number of labeled graphs of bounded treewidth
ترجمه فارسی عنوان
در تعداد گرافهای نشاندار شده از عرض درختی محدود
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
Let Tn,k be the number of labeled graphs on n vertices and treewidth at most k (equivalently, the number of labeled partial k-trees). We show that ck2knlogkn2âk(k+3)2kâ2kâ2â¤Tn,kâ¤k2knn2âk(k+1)2kâk,for k>1 and some explicit absolute constant c>0. Disregarding terms depending only on k, the gap between the lower and upper bound is of order (logk)n. The upper bound is a direct consequence of the well-known formula for the number of labeled k-trees, while the lower bound is obtained from an explicit construction. It follows from this construction that both bounds also apply to graphs of pathwidth and proper-pathwidth at most k.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Combinatorics - Volume 71, June 2018, Pages 12-21
Journal: European Journal of Combinatorics - Volume 71, June 2018, Pages 12-21
نویسندگان
Julien Baste, Marc Noy, Ignasi Sau,