کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
9516180 | 1343767 | 2005 | 4 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The diameter of directed graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
Let D be a strongly connected oriented graph, i.e., a digraph with no cycles of length 2, of order n and minimum out-degree δ. Let D be eulerian, i.e., the in-degree and out-degree of each vertex are equal. Knyazev (Mat. Z. 41(6) 1987 829) proved that the diameter of D is at most 52δ+2n and, for given n and δ, constructed strongly connected oriented graphs of order n which are δ-regular and have diameter greater than 42δ+1n-4. We show that Knyazev's upper bound can be improved to diam(D)⩽42δ+1n+2, and this bound is sharp apart from an additive constant.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 94, Issue 1, May 2005, Pages 183-186
Journal: Journal of Combinatorial Theory, Series B - Volume 94, Issue 1, May 2005, Pages 183-186
نویسندگان
Peter Dankelmann,