کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4648188 1342397 2012 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Mixed unit interval graphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Mixed unit interval graphs
چکیده انگلیسی
The class of intersection graphs of unit intervals of the real line whose ends may be open or closed is a strict superclass of the well-known class of unit interval graphs. We pose a conjecture concerning characterizations of such mixed unit interval graphs, verify parts of it in general, and prove it completely for diamond-free graphs. In particular, we characterize diamond-free mixed unit interval graphs by means of an infinite family of forbidden induced subgraphs, and we show that a diamond-free graph is mixed unit interval if and only if it has intersection representations using unit intervals such that all ends of the intervals are integral.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 312, Issue 22, 28 November 2012, Pages 3357-3363
نویسندگان
, , , , ,