A bound on judicious bipartitions of directed graphs

• 来源期刊: 中国科学：数学（英文版）
• 年，卷（期）: 2020,（2）
• 页码范围: 297-308
• 页数: 12页
• 语种: 英文

摘要

Judicious partitioning problems on graphs ask for partitions that bound several quantities simultaneously,which have received much attention lately.Scott (2005) asked the following natural question:What is the maximum constant cd such that every directed graph D with m arcs and minimum outdegree d admits a bipartition V(D) =V1 ∪ V2 satisfying min{e(V1,V2),e(V2,V1)} ≥ cadm? Here,for i =1,2,e(Vi,V3-i) denotes the number of arcs in D from Vi to V3-i.Lee et al.(2016) conjectured that every directed graph D with m arcs and minimum outdegree at least d ≥ 2 admits a bipartition V(D) =V1 ∪ V2 such that min{e(V1,V2),e(Y2,V1)}≥ (d-1/(22d-1)+o(1))m.In this paper,we show that this conjecture holds under the additional natural condition that the minimum indegree is also at least d.