کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4646875 | 1342316 | 2016 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Diameter and maximum degree in Eulerian digraphs
ترجمه فارسی عنوان
قطر و درجه بالاتر در دیفرانسههای اویلر
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
In this paper we consider upper bounds on the diameter of Eulerian digraphs containing a vertex of large degree. Define the maximum degree of a digraph to be the maximum of all in-degrees and out-degrees of its vertices. We show that the diameter of an Eulerian digraph of order nn and maximum degree ΔΔ is at most n−Δ+3n−Δ+3, and this bound is sharp. We also show that the bound can be improved for Eulerian digraphs with no 2-cycle to n−2Δ+O(Δ2/3)n−2Δ+O(Δ2/3), and we exhibit an infinite family of such digraphs of diameter n−2Δ+Ω(Δ1/2)n−2Δ+Ω(Δ1/2). We further show that for bipartite Eulerian digraphs with no 2-cycle the diameter is at most n−2Δ+3n−2Δ+3, and that this bound is sharp.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 339, Issue 4, 6 April 2016, Pages 1355–1361
Journal: Discrete Mathematics - Volume 339, Issue 4, 6 April 2016, Pages 1355–1361
نویسندگان
Peter Dankelmann, Michael Dorfling,