کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
419202 683753 2016 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Clique cycle-transversals in distance-hereditary graphs
ترجمه فارسی عنوان
متقاطع چرخه دسته در نمودار فاصله ارثی
کلمات کلیدی
متقاطع چرخه. نمودار فاصله ارثی؛ مجموعه راس فیدبک؛ عرضی چرخه دسته؛ خصوصیات زیرگراف القایی ممنوع
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

A cycle transversal or feedback vertex set   of a graph GG is a subset T⊆V(G)T⊆V(G) such that T∩V(C)≠0̸T∩V(C)≠0̸ for every cycle CC of GG. A clique cycle transversal, or cct for short, is a cycle transversal which is a clique. Recognizing graphs which admit a cct can be done in polynomial time; however, no structural characterization of such graphs is known. We characterize distance-hereditary graphs admitting a cct in terms of forbidden induced subgraphs. This extends similar results for chordal graphs and cographs.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 210, 10 September 2016, Pages 38–44
نویسندگان
, , , ,