کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6871963 | 684128 | 2016 | 14 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Bichain graphs: Geometric model and universal graphs
ترجمه فارسی عنوان
نمودارهای بیکین: مدل هندسی و نمودارهای جهانی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
نمودار تقاطع، نمودار جهانی، تقسیم نمودار تعویض،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Bichain graphs form a bipartite analog of split permutation graphs, also known as split graphs of Dilworth number 2. Unlike graphs of Dilworth number 1 that enjoy many nice properties, split permutation graphs are substantially more complex. To better understand the global structure of split permutation graphs, in the present paper we study their bipartite analog. We show that bichain graphs admit a simple geometric representation and have a universal element of quadratic order, i.e. an n-universal bichain graph with n2 vertices. The latter result improves a recent cubic construction of universal split permutation graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 199, 30 January 2016, Pages 16-29
Journal: Discrete Applied Mathematics - Volume 199, 30 January 2016, Pages 16-29
نویسندگان
Robert Brignall, Vadim V. Lozin, Juraj Stacho,