圖二部平衡劃分中的極小反例問題.pdf

1、設(shè)圖G為簡單圖，k為正整數(shù).若將圖G的頂點(diǎn)集V(G)劃分成k個互不相交的頂點(diǎn)集V1，V2,…，Vk，稱為簡單圖G的一個k-部劃分.若圖G的某個k-部劃分，滿足條件-1≤|Vi|-|Vj|≤1，（i，j∈{1，2，…，k}），則稱V1，V2,…，Vk，是圖G的一個k-部平衡劃分，其中|Vi|(i∈k）表示某個劃分的大小即所含頂點(diǎn)個數(shù).
　　本篇學(xué)位論文主要討論k-部劃分中比較特殊的平衡二部劃分問題，即此時k=2.在文獻(xiàn)中，Bollo

2、bás和Scott有一個著名的關(guān)于平衡二部劃分的猜想:對于有m條邊和n個頂點(diǎn)的簡單圖G，若每個頂點(diǎn)的度至少為2，則圖G存在一個平衡二部劃分[V1，V2]，使得max{e(V1)，e(V2)}≤m/3.
　　Xu，Yan和Yu在文獻(xiàn)中初步證明了當(dāng)△(G)≤7/5δ(G)時，圖G的最大平衡二部劃分滿足max{e(V1)，e(V2)}≤e(G)/3.之后，Xu和Yu進(jìn)一步證明猜想的正確性，并指出三角形K3是唯一極圖.
　　Lee，

3、Loh和Sudakov證明了對任意正整數(shù)k≥1，每個有m條邊的圖G，若最小度為2k或2k+1，則圖G有平衡二部劃分[V1，V2]滿足max{e(V1), e(V2)}≤(k+1/2(2k+1)+o(1))m并且他們猜想無窮小的尾數(shù)項(xiàng)可以去掉.
　　本篇學(xué)位論文延用Xu和Yu在文獻(xiàn)中的方法，主要證明了如下結(jié)論:
　　設(shè)圖G是一個最小度不小于4且含m條邊和n個頂點(diǎn)的簡單圖.若圖G沒有二部平衡劃分[S，(S)]，使得max{e(S