کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419494 | 683823 | 2011 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Weighted well-covered graphs without C4C4, C5C5, C6C6, C7C7
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
A graph is well-covered if every maximal independent set has the same cardinality. The recognition problem of well-covered graphs is known to be co-NP-complete. Let ww be a linear set function defined on the vertices of GG. Then GG is ww-well-covered if all maximal independent sets of GG are of the same weight. The set of weight functions ww for which a graph is ww-well-covered is a vector space . We prove that finding the vector space of weight functions under which an input graph is ww-well-covered can be done in polynomial time, if the input graph contains neither C4C4 nor C5C5 nor C6C6 nor C7C7.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 159, Issue 5, 6 March 2011, Pages 354–359
Journal: Discrete Applied Mathematics - Volume 159, Issue 5, 6 March 2011, Pages 354–359
نویسندگان
Vadim E. Levit, David Tankus,