کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6871122 1440178 2018 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Recent results on containment graphs of paths in a tree
ترجمه فارسی عنوان
نتایج اخیر در نمودارهای مهار کردن مسیرها در یک درخت
کلمات کلیدی
پست ها، نمودار مقایسه مدل های انعطاف پذیر هندسی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
In this paper, motivated by the questions posed by Spinrad in Spinrad (2003) and Golumbic and Trenk (2004), we investigate those posets that admit a containment model mapping vertices into paths of a tree and their comparability graphs, named CPT posets and CPT graphs, respectively. We present a necessary condition to be CPT and prove it is not sufficient. We provide further examples of CPT posets P whose dual Pd is non CPT. Thus, we introduce the notion of dually-CPT and strong-CPT posets. We demonstrate that, unlike what happens with posets admitting a containment model using interval of the line, the dimension and the interval dimension of CPT posets is unbounded. On the other hand, we find that the dimension of a CPT poset is at most the number of leaves of the tree used in the containment model. We give a characterization of CPT ( also dually-CPT and strong-CPT) split posets by a family of forbidden subposets. We prove that every tree is strong-CPT.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 245, 20 August 2018, Pages 139-147
نویسندگان
, , ,