On The Properties Of Minimum Counterexamples To A Conjecture On Bisection

Let G be a simple graph.A k-partition of G is a partition of V(G)into k non-empty disjoint subsets V1,V2,...,Vk,and is usually denoted as[V1,V2,...,Vk].When k=2,a 2-partition is simply called a bipartition.If the bipartition meets the require-ment that-1≤|V1|-|V2|<1,then[V1,V2]is called a bisection.In[4],Bollobas and Scott proposed a famous conjecture:If G is a sim-ple graph with δ(G)>2,then G admits a bisection[V1,V2]such that max{e(V1,e(V2)}≤1/3e(G).In[9],Lee,Loh and Sudakov proved that:Every simple graph G with δ(G)=2k or δ(G)=2k+1 admits a bisection[S,S]such that:max{e(S),e(S-)}≤(k+1/2(2k+1)+o(1)m.In[18],Xu,Yan and Yu proof the conclusion that:While △(G)≤7/5δ(G),G admits a bisection[V1,V2]that max{e(V1),e(V2)}≤m/3.The conjecture of Bollobas and Scott have been proved by Xu and Yu in[19].While k=3 we consider the question that whether every simple graph with δ(G)≥6 admits a bisection with max{e(S),e(-S)}≤2/7m.In this dissertation,we obtain the following result:Suppose X={G|G is a simple graph with m edges and n vertices,δ(G)>6,each bisection[S,-S]of G has max{e(S),e(-S)}>2/7m},and let G be the element of Y with minimum order.If x1,x2,x3,x4,x5,x6∈V(G),G[x1,x2,x3,x4,x5,x6)≈=K6,dG(xi)=6,1≤i≤6,then...