【摘要】：我們用g(s,t)來(lái)表示最小的整數(shù)使得給定兩個(gè)非負(fù)整數(shù)S和t,當(dāng)圖G滿(mǎn)足δ(G)≥g(s,t)時(shí),這個(gè)圖的點(diǎn)集V(G)可以劃分為兩個(gè)部分V1和V2,兩個(gè)部分的導(dǎo)出子圖分別滿(mǎn)足δ(G[V1])≥s以及δ(G[V2])≥ t.Stiebitz已經(jīng)證明了g(s,t)≤s+t+1,Kaneko和Diwan分別在特殊圖類(lèi)上改進(jìn)了這個(gè)結(jié)果,證明出了G滿(mǎn)足g(G)≥4時(shí)g(s,t)≤s+t (s,t≥1),或者當(dāng)G滿(mǎn)足g(G)≥5時(shí)有g(shù)(s,t)≤s+t-1 (s,t≥2),其中g(shù)(G)是圖G的圍長(zhǎng).Liu和Xu進(jìn)一步強(qiáng)化了Kaneko和Diwan的結(jié)果,證明了當(dāng)圖G不是K3且無(wú)(K4-e)結(jié)構(gòu)時(shí)有g(shù)(s,t)≤s+t(s,t≥1)和當(dāng)圖G滿(mǎn)足在無(wú)3-圈的圖下沒(méi)有兩個(gè)4-圈共邊結(jié)構(gòu)時(shí)有g(shù)(s,t)≤s+f-1(s,t≥2).Bazgan,Tuza和Vanderpooten分別根據(jù)Stiebitz,Kaneko和Diwan的證明給出了可以在多項(xiàng)式時(shí)間內(nèi)可以找出這些劃分的算法.在本學(xué)位論文中,我們根據(jù)Liu和Xu的證明給出相應(yīng)的可以在多項(xiàng)式時(shí)間內(nèi)找出這些劃分的算法.
【學(xué)位授予單位】：南京師范大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2016
【分類(lèi)號(hào)】：O157.5

【相似文獻(xiàn)】

相關(guān)會(huì)議論文 前1條

1 劉澄玉;趙莉娜;;一種基于節(jié)點(diǎn)劃分的Ad Hoc網(wǎng)絡(luò)模型[A];2008通信理論與技術(shù)新發(fā)展——第十三屆全國(guó)青年通信學(xué)術(shù)會(huì)議論文集（下）[C];2008年

相關(guān)碩士學(xué)位論文 前1條

1 王巧蕓;度約束下頂點(diǎn)劃分的算法[D];南京師范大學(xué);2016年

，

本文編號(hào)：2534423