کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
9516180 1343767 2005 4 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The diameter of directed graphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
The diameter of directed graphs
چکیده انگلیسی
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
نویسندگان
,