کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10224215 | 1701084 | 2018 | 13 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Encoding and avoiding 2-connected patterns in polygon dissections and outerplanar graphs
ترجمه فارسی عنوان
رمزگذاری و اجتناب از الگوهای دو جانبه در جداول چندگانه و نمودارهای بیرونی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
Let Î={δ1,δ2,â¦,δm} be a finite set of 2-connected patterns, i.e. graphs up to vertex relabelling. We study the generating function DÎ(z,u1,u2,â¦,um), which counts polygon dissections and marks subgraph copies of δi with the variable ui. We prove that this is always algebraic, through an explicit combinatorial decomposition depending on Î. The decomposition also gives a defining system for DÎ(z,0), which encodes polygon dissections that avoid these patterns as subgraphs. In this way, we are able to extract normal limit laws for the patterns when they are encoded, and perform asymptotic enumeration of the resulting classes when they are avoided. The results can be transferred to the case of labelled outerplanar graphs. We give examples and compute the relevant constants when the patterns are small cycles or dissections.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 341, Issue 12, December 2018, Pages 3402-3414
Journal: Discrete Mathematics - Volume 341, Issue 12, December 2018, Pages 3402-3414
نویسندگان
Vasiliki Velona,