Upper bounds on minimum balanced bipartitions
Upper bounds on minimum balanced bipartitions
复制标题
DOI：
10.1016/j.disc.2011.11.030
复制
发表时间：
2012-03
期刊：
影响因子：
--
通讯作者：
G. Fan;Baogang Xu;Xingxing Yu;Chuixiang Zhou
中科院分区：
文献类型：
--
作者：
G. Fan;Baogang Xu;Xingxing Yu;Chuixiang Zhou
图 G 的平衡二分是将 V(G) 划分为两个子集 V1 和 V2，它们的大小最多相差 1。最小平衡二分问题要求图的平衡二分 V1,V2 最小化 e(V1,V2)，其中 e(V1,V2) 是连接 V1 和 V2 的边数。我们提出了 e(V1,V2) 最小值的严格上限，为 Bollobás 和 Scott 的问题提供了一个答案。我们证明每个至少 3 阶的连通无三角形平面图 G 都具有平衡二分 V1,V2，其中 e(V1,V2)≤|V(G)|−2，并且证明 K1,3、K3,3−e 和 K2,n（其中 n≥1）正是极值图。我们还证明，每个不分离三角形的平面图 G 都有一个平衡二分 V1,V2，使得 e(V1,V2)≤|V(G)|+1。
A balanced bipartition of a graph G is a partition of V(G) into two subsets V1and V2, which differ in size by at most 1. The minimum balanced bipartition problem asks for a balanced bipartition V1,V2of a graph minimizing e(V1,V2), where e(V1,V2) is the number of edges joining V1and V2. We present a tight upper bound on the minimum of e(V1,V2), giving one answer to a question of Bollobás and Scott. We prove that every connected triangle-free plane graph G of order at least 3 has a balanced bipartition V1,V2with e(V1,V2)≤|V(G)|−2, and we show that K1,3, K3,3−e, and K2,n, with n≥1, are precisely the extremal graphs. We also show that every plane graph G without separating triangles has a balanced bipartition V1,V2such that e(V1,V2)≤|V(G)|+1.