Balanced Partitions Of Graphs

Let k be a positive integer, a k-partition of graph G is a partition of V(G) into k pairwise disjoint nonempty sets. A k-partition V1, V2,..., Vk of a graph G is said to be balanced if-1≤|Vi|-|Vj|≤1for1≤i, j≤k. In this dissertation, we study balanced partition problems.Given a partition V1,..., Vk of V(G), we use e(Vi) to denote the number of edges in the subgraph of G induced by Vi, and let e(V1,...,Vk)=|E(G)|-Σi=1ke(Vi). Usu ally, e(V1, V2,..., Vk) is referred to as the size of the partition. One of our concerning problems is to find a balanced partition V1,..., Vk that rninimums e(V1,..., Vk). In contrast to this problem, we can also consider "judicious" partition problem which asks for a partition V1,...,Vk maximizing min{e(Vi): i=1,..., k}. In [18], Bol-lobas and Scott asked that: for a graph G with n vertices and m edges, what are the largest and smallest sizes that we can guarantee with balanced bipartitions?Recently, Xu, Yan and Yu [76] proved that every graph with m edges has a bal-anced bipartition of size at least m+|M|/2, where M is a matching of G. The bound is sharp as evidenced by the complete graphs of odd order. Fan et al.[31] proved that ev-ery graph G has a minimum balanced bipartition of size at most1/2(|E(G)|+[|V(G)/2|-|M|), where M is a maximum matching of the complement graph of G. The bound of Theorem1.2.2is again sharp on complete graphs.A folklore conjecture (see [31]) claims that every plane graph of order n has a balanced bipartition V1, V2such that e(V1, V2)≤n. If this conjecture is true, the bound is best possible, as shown by K4.Let G be a plane graph of order n. In [31], Fan et al. proved that if G has no separating triangle then it admits a balanced bipartition of size at most n+1, they also proved that every connected triangle-free plane graph of order n>3has a balanced bipartition V1,V2such that e(V1,V2)<n—2. The extremal graphs are precisely K1,3,K3,3-e and K2,k,k≥1.In [18], Bollotas and Scott also conjectured that: every graph G with m edges and minimum degree at least2admits a balanced partition V1, V2such that max{e(V1),e(V2)}≤m/3.Xu, Yan and Yu [75] proved that if A(G)≤7/5δ(G), then every maximum bal-anced bipartition of G has the property that max{e(V1), e(V2)}≤e(G)/3.In Chapter2, we first strengthen the upper bound of Fan et al.’s result on mini-mum balanced bipartition of triangle-free graphs to m+1/2. Then we show that every2-connected graph G admits a balanced bipartition V1, V2such that the subgraphs of G induced by V1and by V2are both connected. This yields a good upper bound to the size of minimum balanced bipartition of sparse graphs. We also present an up-per bound of the size of minimum balanced bipartitions of triangle-free plane graphs which improves the corresponding bound of Fan et al.’s latter result. To be precisely, we prove that (1) if either5(G)≥2or g≤6, then G admits a balanced bipartition of size at most [g(n-2)/g-2]-n+2;(2) if5(G)=1and g≥7, then G admits a balanced bipartition of size at most[g(n-2)/2(g-2)]-1In Chapter3, contrary to [75], we consider the judicious partitions related to the minimum balanced bipartition problem, and following the same method we prove that if G is a graph with n vertices and m edges, and r is a real number of greater than4, then (1) G admits a minimum balanced bipartition V1, V2such that min{e(V1), e(V2)}≥(k-1)m/4k if it is k-regular with k≥3; and (2) G admits a minimum balanced bipartition such that min{e(V1), e(V2)}≥m/r provided that△(G)≤3r-4/r+4δ(G)-2r/r+4if n is even, and that△(G)≤3r-4/r+4δ(G)-8r/r+4if n is odd, where e(Vi) denotes the number of edges of G with both ends in Vi.In Chapter4, we extend the idea used on the maximum bisection in [54] to the balanced3-partitions. Let G be a graph with m edges, and let r be the maximum number of vertex-disjoint2-paths, where a2-path stands for a path of length2. We show that G admits a balanced3-partition Vx, V2, V3such that e(V1,V2, V3)≥2m+2r/3. We also present, for each real number3≤p<6, a sufficient condition that G admits a maximum balanced3-partition V1, V2, V3with max{e(V1), e(V2), e(V3)}≤m/p.In Chapter5, instead of considering maximum balanced3-partitions, we investi-gate in minimum balanced k-partitions. For k=3,4, we respectively present an upper bound on minimum e(V1, V2,…, Vk). Moreover, we show that if G is a graph with m edges, then G admits a minimum balanced3-partition such that e(V1, V2, V3)≤2m/3+[n/3]+1/3, and G admits a minimum balanced4-partition such that e(V1, V2, F3, V4)≤3m/4+3/2[n/4]+3/4At the end of this dissertation, we propose some problems for further researches.