کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
418370 681656 2013 23 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Normal Helly circular-arc graphs and its subclasses
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Normal Helly circular-arc graphs and its subclasses
چکیده انگلیسی

A Helly circular-arc model M=(C,A)M=(C,A) is a circle CC together with a Helly family AA of arcs of CC. If no arc is contained in any other, then MM is a proper Helly circular-arc model, if every arc has the same length, then MM is a unit Helly circular-arc model, and if there are no two arcs covering the circle, then MM is a normal Helly circular-arc model. A Helly (resp. proper Helly, unit Helly, normal Helly) circular-arc graph is the intersection graph of the arcs of a Helly (resp. proper Helly, unit Helly, normal Helly) circular-arc model. In this article we study these subclasses of Helly circular-arc graphs. We show natural generalizations of several properties of (proper) interval graphs that hold for some of these Helly circular-arc subclasses. Next, we describe characterizations for the subclasses of Helly circular-arc graphs, including forbidden induced subgraphs characterizations. These characterizations lead to efficient algorithms for recognizing graphs within these classes. Finally, we show how these classes of graphs relate with straight and round digraphs.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 161, Issues 7–8, May 2013, Pages 1037–1059
نویسندگان
, , ,