کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
418783 681718 2014 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Which kk-trees are cover–incomparability graphs?
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Which kk-trees are cover–incomparability graphs?
چکیده انگلیسی

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
نویسندگان
, , , ,