度約束下頂點(diǎn)劃分的算法.pdf

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

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