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 c...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 cdsuch that every directed graph D with m arcs and minimum outdegree d admits a bipartition V(D)=V_1∪V_2 satisfying min{e(V_1,V_2),e(V_2,V_1)}cdm?Here,for i=1,2,e(V_i,V_(3-i))denotes the number of arcs in D from V_i to V_(3-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)=V_1∪V_2 such that min{e(V_1,V_2),e(V_2,V_1)}≥((d-1)/(2(2 d-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.展开更多
An oriented tripartite graph is the result of assigning a direction to each edge of a simple tripartite graph. For any vertex x in an oriented tripartite graph D（U, V, W）, let dx^＋ and dx^- denote the outdegree and...An oriented tripartite graph is the result of assigning a direction to each edge of a simple tripartite graph. For any vertex x in an oriented tripartite graph D（U, V, W）, let dx^＋ and dx^- denote the outdegree and indegree respectively of x. Define aui： dui^＋ - dus^-, bvj = dvj^＋ - dvj^- and cwk = dwk^＋ - dwk^- as the imbalances of the vertices ui in U, vj in V and wk in W respectively. In this paper, we obtain criteria for sequences of integers to be the imbalances of some oriented tripartite graph. Keywords Digraph, imbalance, outdegree, indegree, oriented graph, oriented tripartite graph, arc展开更多
基金supported by National Natural Science Foundation of China (Grant No. 11671087)supported by National Science Foundation of USA (Grant No. DMS1600738)+2 种基金the Hundred Talents Program of Fujian Provincesupported by the Shandong Provincial Natural Science Foundation of China (Grant No. ZR2014JL001)the Excellent Young Scholars Research Fund of Shandong Normal University of China
文摘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 cdsuch that every directed graph D with m arcs and minimum outdegree d admits a bipartition V(D)=V_1∪V_2 satisfying min{e(V_1,V_2),e(V_2,V_1)}cdm?Here,for i=1,2,e(V_i,V_(3-i))denotes the number of arcs in D from V_i to V_(3-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)=V_1∪V_2 such that min{e(V_1,V_2),e(V_2,V_1)}≥((d-1)/(2(2 d-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.
文摘An oriented tripartite graph is the result of assigning a direction to each edge of a simple tripartite graph. For any vertex x in an oriented tripartite graph D（U, V, W）, let dx^＋ and dx^- denote the outdegree and indegree respectively of x. Define aui： dui^＋ - dus^-, bvj = dvj^＋ - dvj^- and cwk = dwk^＋ - dwk^- as the imbalances of the vertices ui in U, vj in V and wk in W respectively. In this paper, we obtain criteria for sequences of integers to be the imbalances of some oriented tripartite graph. Keywords Digraph, imbalance, outdegree, indegree, oriented graph, oriented tripartite graph, arc
