کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4650209 1342479 2009 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The stable set polytope for some extensions of P4P4-free graphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
The stable set polytope for some extensions of P4P4-free graphs
چکیده انگلیسی

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