度約束下頂點劃分的算法.pdf

1、我們用g(s，t)來表示最小的整數(shù)使得給定兩個非負(fù)整數(shù)s和t，當(dāng)圖G滿足δ(G)≥g(s，t)時，這個圖的點集V(G)可以劃分為兩個部分V1和V2，兩個部分的導(dǎo)出子圖分別滿足δ（G[V1]）≥s以及δ（G[V2）≥t.Stiebitz已經(jīng)證明了g(s，t)≤s+t+1，Kaneko和Diwan分別在特殊圖類上改進(jìn)了這個結(jié)果，證明出了G滿足g(G)≥4時g(s，t)≤s+t(s，t≥1)，或者當(dāng)G滿足g(G)≥5時有g(shù)(s，t)≤s+t-

2、1(s，t≥2)，其中g(shù)(G)是圖G的圍長.Liu和Xu進(jìn)一步強(qiáng)化了Kaneko和Diwan的結(jié)果，證明了當(dāng)圖G不是K3且無(K4-e)結(jié)構(gòu)時有g(shù)(s，t)≤ s+t(s，t≥1)和當(dāng)圖G滿足在無3-圈的圖下沒有兩個4-圈共邊結(jié)構(gòu)時有g(shù)(s，t)≤s+t-1(s，t≥2).
　　Bazgan，Tuza和Vanderpooten分別根據(jù)Stiebitz，Kaneko和Diwan的證明給出了可以在多項式時間內(nèi)可以找出這些劃分的算法.在