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

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
نویسندگان
, ,