کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
418783 | 681718 | 2014 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Which kk-trees are cover–incomparability graphs?
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
In this paper we deal with cover–incomparability graphs of posets. It is known that the class of cover–incomparability graphs is not closed on induced subgraphs which makes the study of structural properties of these graphs difficult. In this paper we introduce the notion of s-subgraph which enables us to define forbidden s-subgraphs (i.e. graphs that cannot appear as s-subgraphs of any cover–incomparability graph). We show that the family of minimal forbidden s-subgraphs is infinite even for cover–incomparability unit-interval graphs. Using the notion of s-subgraph we also answer the question which kk-trees are cover–incomparability graphs and which chordal graphs without K4K4 are cover–incomparability graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 167, 20 April 2014, Pages 222–227
Journal: Discrete Applied Mathematics - Volume 167, 20 April 2014, Pages 222–227
نویسندگان
Jana Maxová, Miroslava Dubcová, Pavla Pavlíková, Daniel Turzík,