کد مقاله کد نشریه سال انتشار مقاله انگلیسی ترجمه فارسی نسخه تمام متن
5777342 1632750 2018 14 صفحه PDF سفارش دهید دانلود کنید
عنوان انگلیسی مقاله ISI
Packing and covering odd cycles in cubic plane graphs with small faces
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI
فقط 3 هزار تومان
سفارش ترجمه تخصصی
با تضمین قیمت و کیفیت
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Packing and covering odd cycles in cubic plane graphs with small faces
چکیده انگلیسی

We show that any 3-connected cubic plane graph on n vertices, with all faces of size at most 6, can be made bipartite by deleting no more than (p+3t)n∕5 edges, where p and t are the numbers of pentagonal and triangular faces, respectively. In particular, any such graph can be made bipartite by deleting at most 12n∕5 edges. This bound is tight, and we characterise the extremal graphs. We deduce tight lower bounds on the size of a maximum cut and a maximum independent set for this class of graphs. This extends and sharpens the results of Faria et al. (2012).

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Combinatorics - Volume 67, January 2018, Pages 208-221
نویسندگان
, ,
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI
فقط 3 هزار تومان
سفارش ترجمه تخصصی
با تضمین قیمت و کیفیت