کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
8903891 | 1632965 | 2018 | 30 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On box-perfect graphs
ترجمه فارسی عنوان
در جعبه نمودار کامل
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
Let G=(V,E) be a graph and let AG be the clique-vertex incidence matrix of G. It is well known that G is perfect iff the system AGxâ¤1, xâ¥0 is totally dual integral (TDI). In 1982, Cameron and Edmonds proposed to call G box-perfect if the system AGxâ¤1, xâ¥0 is box-totally dual integral (box-TDI), and posed the problem of characterizing such graphs. In this paper we prove the Cameron-Edmonds conjecture on box-perfectness of parity graphs, and identify several other classes of box-perfect graphs. We also develop a general and powerful method for establishing box-perfectness.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 128, January 2018, Pages 17-46
Journal: Journal of Combinatorial Theory, Series B - Volume 128, January 2018, Pages 17-46
نویسندگان
Guoli Ding, Wenan Zang, Qiulan Zhao,