圖的等全著色及相關(guān)問題研究.pdf

1、圖論是組合數(shù)學(xué)和離散數(shù)學(xué)最重要的分支之一，也是計算機(jī)科學(xué)、運(yùn)籌學(xué)、系統(tǒng)科學(xué)的重要基礎(chǔ)。圖論的研究不僅具有重要的理論價值而且具有重要的應(yīng)用背景，它已被廣泛地用來解決信息科學(xué)、計算機(jī)科學(xué)、網(wǎng)絡(luò)理論等學(xué)科的問題，并被應(yīng)用于物理學(xué)、化學(xué)、生物學(xué)等領(lǐng)域的某些分支學(xué)科。在圖論這一重要研究領(lǐng)域，本文的研究工作集中在圖的著色及其相關(guān)領(lǐng)域，將計算機(jī)搜索和數(shù)學(xué)證明相結(jié)合，對廣義Petersen圖P(n，k)等圖的等全著色、(d，1)全標(biāo)號、非正則全標(biāo)號、2

2、-彩虹支配四個方面的課題進(jìn)行了研究。所取得的主要結(jié)果包括： 1.在等全著色方面，研究了廣義Petersen圖P(n，k)、FlowerSnark及其相關(guān)圖、Glod-bergSnark及其相關(guān)圖、兩個圈的交圖Cm□Cn的等全著色問題，證明了廣義Petersen圖P(n，k)(k(mod16)≠0并且(n，k)(∈){(5，1)，(9，3)})、FlowerSnark及其相關(guān)圖、GoldbergSnark及其相關(guān)圖的等全色數(shù)是4；

3、Cm□Cn的等全色數(shù)是5。 2.在圖的(d，1)全標(biāo)號方面，證明了如果圖G是r-正則非二部圖并且d≥r≥3，則λTd(G)≥d+r+1.研究了廣義Petersen圖P(n，k)、FlowerSnark及其相關(guān)圖、GoldbergSnark及其相關(guān)圖的(d，1)全標(biāo)號，證明了廣義Petersen圖(n是奇數(shù)或k是偶數(shù))、FlowerSnark及其相關(guān)圖(n是奇數(shù))、GoldbergSnark及其相關(guān)圖d≥3時的(d，1)全標(biāo)號數(shù)是

4、d+4;Flowersnark及其相關(guān)圖(n是奇數(shù))、GoldbergSnark及其相關(guān)圖的(2，1)-全標(biāo)號數(shù)是5。 3.在非正則全標(biāo)號方面，研究了廣義Petersen圖P(n，k)、梯子圖Ln、莫比烏斯梯子圖Mn、Kn(o)del圖W3.n、FlowerSnark及其相關(guān)圖和兩個圈的交圖Cm□Cn的非正則全標(biāo)號問題，證明了上述圖類邊非正則全標(biāo)號強(qiáng)度等于[|E(G)|+2/3]，點(diǎn)非正則全標(biāo)號強(qiáng)度等于[|V(G)|+δ/△+1