Some Results On Balanced Bipartitions Problems Of Graphs

Let G be a simple graph. If V(G) = Vi U V2,V1∩V2 = 0 and V1≠(?)≠V2, then (Vi, V2) is said to be a partition of G. Let (V1, V2) be a partition of G. If||V1| - |V2|| ≤ 1, then (Vi, V2) is said to be a bisection of G. It is meaningless to talk bisections without any further restriction. In this thesis, we deal with two kinds of bisection problems: one is bisection with restriction on the number of edges, and the other is with restriction on the degree of vertices.In [8], Bollobas and Scott proposed a conjecture as follow: If G is a simple graph with δ(G) > 2, then G has a bisection (S,S) such that max{e(S),e((?))} ≤1/3m(G),where e(S) is the number of edges in the subgargh induced by S. On the other hand, Lee, Loh, and Sudakov [17] proved that if G is a simple graph with δ(G) = 2k or 2+ 1,then G has a bisection (S,S) such that max{e(S),e((?))} ≤ 2(2k+1 /(2k+1)+0(1))m(G). In 2014, Xu and Yu [29] confirmed the conjecture of Bollobas and Scott and characterized the unique extremal graph K3. Now, we are interested in whether the result of Lee, Loh, and Sudakov holds with the o(1) term removed in the case of k= 2.In other words, we want to know whether a simple graph G with δ(G) ≥ 4 has a bisection (S,S) such that max{e(S), e((?))}≤3/10m(G) . Since the statement hold on small graphs,we try study the structure of minmum counterexample to the statement.We prove the following result: Let X = {G : 8(G) > 4, each bisection [S, S] of G satisfies max {e(S), e((?))} > 3/10e(G)},and let G be a graph with minimum order in X. If v1, v2,v3,v4 are four vertices of degree 4 such that G[(v1,v2,v3,v4]≌ K4,then |((?) N(vi) \{v1,v2:v3, v4)}≠3,4; If |((?)N(vi) \ {v1,v2,v3,v4})|=2, thenGraph 1 below is not subgraph of G, expect n is even and m mod(10)≡ 3; and Graph 2 below is not subgraph of G, expect n is even and m ∈ {3,6,9} mod(10).The second main result of this paper is bisection under degree constraint. Let(A, B) be a partition of G. If (?)x ∈ A, dA(x) ≥ dB(x) and (?)y ∈ B, dB(y) ≥ dA(y),then (A, B) is called a internal partition of G. In 2014, Liu and Xu [19] prove that each graph G with (δ(G) ≥ 2 has (1:1)- bisection (S, S) such that δ(S) + ((?))≥ d-1.Inspired by the idea of [18], we prove the following conclusion: Let d≥ 5 and G be a d-regular graph without internal partition. Then G admits a (2,2)- bisection (S, S)such that δ(S) +((?))≥ d - 1.