کد مقاله کد نشریه سال انتشار مقاله انگلیسی ترجمه فارسی نسخه تمام متن
4653204 1343071 2017 5 صفحه PDF ندارد دانلود کنید
عنوان انگلیسی مقاله
Improved bound on the oriented diameter of graphs with given minimum degree
ترجمه فارسی عنوان
مرز بهبودیافته بر روی قطر گرا از نمودارها با توجه به حداقل درجه داده شده
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

In 2015, Bau and Dankelmann showed that every bridgeless graph GG of order nn and minimum degree δδ has an orientation of diameter at most 11nδ+1+9. As they were convinced that this bound is not best possible, they posed the problem of improving it.In this paper, we prove that such a graph GG has an orientation of diameter less than 7nδ+1 and give a polynomial-time algorithm to construct one.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Combinatorics - Volume 59, January 2017, Pages 187–191
نویسندگان
,