| Let G be a simple graph, k be a positive integer. If all vertices V(G) of a graph G into k pairwise disjoint non-empty sets, say V1, V2,..., Vk, it called a k-partition of G. For 1≤i, j≤k, when -1|Vi|-|Vj|≤ 1, the k-partition is called a balanced k-partition.In this dissertation, we mainly study the bisection problems. When k=2, the k-balanced partition problems became bisection problems. Bollotas and S-cott put forward a famous conjecture:every graph G with m edges and n ver-tices and minimum degree at least 2 admits a balanced partition [V1, V2] such that max{e(V1),e(V2)ï½â‰¤m/3.Xu, Yan and Yu first proved that when â–³(G)≤7/5δ9G), the maximum balanced bipartition [V1, V2] of G admits max{e(V1), e(V2)}≤e(G)/3. Not long afterwards, Xu and Yu gave a proof to the conjunctive and pointed out the triangle K3 is the only extremal graph.Lee, Loh and Sudakov proved that:every graph G with m edges and n vertices and minimum degree at least 2k or 2k+1 admits a bisection [V1, V2] such thatAnd they also conjectured that the o(1) term can be removed.In this dissertation, we study the above conjecture of Lee, Loh and Sudakov while k= 2 and obtain the following result:Let G be a graph of order n and size m with minimum degree at least 4. If G has no bisection [S, S) with max{e(S), e(S)}≤3/10m, but any graph H of order less than n and minimum degree at least 4 has a bisection [T, T] with max{e(T), e(T)}≤ 3/10e(H),then for any four 4-vertices u1,u2,u3,u4 with G[{u1,u2,u3,u4 )]=K4, unless has the following configurations. |
