کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
436882 | 690047 | 2013 | 4 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Three-matching intersection conjecture for perfect matching polytopes of small dimensions
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
In the study of Fulkerson’s conjecture, Fan and Raspaud (1994) proposed a weaker conjecture: in every bridgeless cubic graph G, there are three perfect matchings M1, M2, and M3 such that M1∩M2∩M3=0̸. In this note we prove that this conjecture is true if the dimension of the perfect matching polytope of G is at most 9. This includes the class of bridgeless cubic graphs with the property that all the vertices of the corresponding perfect matching polytope are affinely independent.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 482, 22 April 2013, Pages 111-114
Journal: Theoretical Computer Science - Volume 482, 22 April 2013, Pages 111-114