کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
419622 683842 2013 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Which distance-hereditary graphs are cover–incomparability graphs?
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Which distance-hereditary graphs are cover–incomparability graphs?
چکیده انگلیسی

In this paper we deal with cover–incomparability graphs of posets, or briefly C–I graphs. These are graphs derived from posets as the edge-union of their cover graph and their incomparability graph. We answer two recently posed open questions. Which distance-hereditary graphs are C–I graphs? Which Ptolemaic (i.e. chordal distance-hereditary) graphs are C–I graphs? It follows that C–I graphs can be recognized efficiently in the class of all distance-hereditary graph whereas recognizing C–I graphs in general is known to be NP-complete.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 161, Issues 13–14, September 2013, Pages 2095–2100
نویسندگان
, ,