کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4651647 1632581 2015 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On containment graphs of paths in a tree
ترجمه فارسی عنوان
در نمودارهای مهارتی مسیرها در یک درخت
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

The aim of the present work is the study of those posets that admit a containment model mapping vertices into paths of a tree, and their comparability graphs named CPT graphs. Answering a question posed by J.Spinrad, we prove that the dimension of CPT graphs is unbounded. We show that every tree is CPT. When ever transitive orientation of the edges of a comparability graph G defines a CPT poset, we say that G is strong-CPT. When both some transitive orientation of G and its reverse are CPT, we say that G is dually-CPT. Split comparability graphs that are dually-CPT or strong-CPT are characterized by forbidden induced subgraphs.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 50, December 2015, Pages 175-180