کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419202 | 683753 | 2016 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Clique cycle-transversals in distance-hereditary graphs
ترجمه فارسی عنوان
متقاطع چرخه دسته در نمودار فاصله ارثی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
متقاطع چرخه. نمودار فاصله ارثی؛ مجموعه راس فیدبک؛ عرضی چرخه دسته؛ خصوصیات زیرگراف القایی ممنوع
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
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
Journal: Discrete Applied Mathematics - Volume 210, 10 September 2016, Pages 38–44
نویسندگان
Andreas Brandstädt, Simone Esposito, Loana T. Nogueira, Fábio Protti,