کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4648723 1342426 2010 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Diamond-free circle graphs are Helly circle
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Diamond-free circle graphs are Helly circle
چکیده انگلیسی

The diamond   is the graph obtained from K4K4 by deleting an edge. Circle graphs are the intersection graphs of chords in a circle. Such a circle model has the Helly property if every three pairwise intersecting chords intersect in a single point, and a graph is Helly circle if it has a circle model with the Helly property. We show that the Helly circle graphs are the diamond-free circle graphs, as conjectured by Durán. This characterization gives an efficient recognition algorithm for Helly circle graphs.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 310, Issue 4, 28 February 2010, Pages 845–849
نویسندگان
, , ,