کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4650209 | 1342479 | 2009 | 12 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The stable set polytope for some extensions of P4P4-free graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
For some graph classes defined by forbidding one-vertex extensions of the P4P4, we introduce an implicit description of the stable set polytope; furthermore, for some of those classes, we give explicitly a minimal defining linear system. This is of interest since the class of P4P4-free graphs is basic in modular decomposition theory, and at the same time a well-known result of Chvátal [V. Chvátal, On certain polytopes associated with graphs, Journal of Combinatorial Theory Series (B) 18 (1975) 138–154] provides a strict link between modular decomposition of graphs and their stable set polytope.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 309, Issue 1, 6 January 2009, Pages 176–187
Journal: Discrete Mathematics - Volume 309, Issue 1, 6 January 2009, Pages 176–187
نویسندگان
Raffaele Mosca,