کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
8903837 | 1632961 | 2018 | 27 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Bipartitions of oriented graphs
ترجمه فارسی عنوان
دو طرفه نمودار گرا
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
Let V(D)=XâªY be a bipartition of a directed graph D. We use e(X,Y) to denote the number of arcs in D from X to Y. Motivated by a conjecture posed by Lee, Loh and Sudakov (2016) [16], we study bipartitions of oriented graphs. Let D be an oriented graph with m arcs. In this paper, it is proved that if the minimum degree of D is δ, then D admits a bipartition V(D)=V1âªV2 such that minâ¡{e(V1,V2),e(V2,V1)}â¥(δâ14δ+o(1))m. Moreover, if the minimum semidegree d=minâ¡{δ+(D),δâ(D)} of D is at least 21, then D admits a bipartition V(D)=V1âªV2 such that minâ¡{e(V1,V2),e(V2,V1)}â¥(d2(2d+1)+o(1))m. Both bounds are asymptotically best possible.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 132, September 2018, Pages 107-133
Journal: Journal of Combinatorial Theory, Series B - Volume 132, September 2018, Pages 107-133
نویسندگان
Jianfeng Hou, Shufei Wu,