兩類正則圖的鄰點(diǎn)全和可區(qū)別全染色

常景智，楊超，程銀萬(wàn)，王芹，姚兵

1.上海工程技術(shù)大學(xué) 數(shù)理與統(tǒng)計(jì)學(xué)院 智能計(jì)算與應(yīng)用統(tǒng)計(jì)研究中心，上海 201620；2.西北師范大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，蘭州 730070

圖的可區(qū)別染色問(wèn)題是圖論中的經(jīng)典問(wèn)題之一，隨著可區(qū)別染色問(wèn)題被廣泛應(yīng)用于計(jì)算機(jī)科學(xué)、生物學(xué)以及網(wǎng)絡(luò)安全等領(lǐng)域，這一問(wèn)題被越來(lái)越多的國(guó)內(nèi)外學(xué)者所研究．近年來(lái)，關(guān)于把點(diǎn)和邊所染顏色相加的可區(qū)別染色問(wèn)題引起了人們的極大關(guān)注．文獻(xiàn)[1]介紹和研究了圖的鄰和可區(qū)別邊染色，并提出下述著名的1-2-3猜想：

猜想1[1](1-2-3猜想) 設(shè)G為一個(gè)階數(shù)至少為3的簡(jiǎn)單連通圖，則gndiΣ(G)≤3．

文獻(xiàn)[2]證明了階數(shù)至少為3的簡(jiǎn)單連通圖的鄰和可區(qū)別邊色數(shù)不超過(guò)5．關(guān)于鄰和可區(qū)別邊染色的相關(guān)研究見(jiàn)文獻(xiàn)[3-6]．文獻(xiàn)[7]提出了圖的鄰和可區(qū)別全染色的概念，并給出了此定義下的1-2猜想：

猜想2[7](1-2猜想) 設(shè)G為一個(gè)簡(jiǎn)單連通圖，則tgndiΣ(G)≤2．

文獻(xiàn)[8]得到了任意圖的鄰和可區(qū)別全色數(shù)不超過(guò)3．文獻(xiàn)[9]考慮把任意點(diǎn)的關(guān)聯(lián)邊與其鄰點(diǎn)所染顏色相加，定義了圖的鄰點(diǎn)被擴(kuò)展和可區(qū)別全染色，且得到了一些特殊圖的鄰點(diǎn)被拓展和可區(qū)別全色數(shù)．文獻(xiàn)[10]研究了仙人掌圖的鄰點(diǎn)被拓展和可區(qū)別全染色．不僅如此，文獻(xiàn)[9]又在鄰點(diǎn)被擴(kuò)展和可區(qū)別全染色的基礎(chǔ)上考慮加上點(diǎn)本身的顏色，介紹了下述關(guān)于圖的一類新染色——鄰點(diǎn)全和可區(qū)別全染色：

其中

N(x)={y∈V(G)|xy∈E(G)}

對(duì)任意的邊uv∈E(G)，如果有φ(u)≠φ(v)成立，則稱f是圖G的一個(gè)鄰點(diǎn)全和可區(qū)別(簡(jiǎn)記NFSD)k-全染色．圖G的鄰點(diǎn)全和可區(qū)別全染色中最小的k值稱為G的鄰點(diǎn)全和可區(qū)別全色數(shù)，記為fgndiΣ(G)．

本文研究了廣義Petersen圖和循環(huán)圖的鄰點(diǎn)全和可區(qū)別全染色問(wèn)題，確定了它們的鄰點(diǎn)全和可區(qū)別全色數(shù)．文中涉及的染色均為非正常的，不失一般性，約定下文證明過(guò)程中凡是未被染色的點(diǎn)和邊均染顏色1．

1 廣義Petersen圖

定理1當(dāng)n為偶數(shù)，k為奇數(shù)時(shí)，fgndiΣ(P(n，k))=2； 其他情形時(shí)，fgndiΣ(P(n，k))≤3．

由定義2知P(n，k)是一類三正則圖，則fgndiΣ(P(n，k))≥2．定理1分以下3個(gè)引理證明：

引理1當(dāng)n為偶數(shù)，k為奇數(shù)時(shí)，fgndiΣ(P(n，k))=2．

證定義P(n，k)的一個(gè)2-全染色f：f(aiai+1)=f(aibi)=f(aibi+k)=1，f(ai)=2(i為奇數(shù))，f(bi)=2(i為偶數(shù))．由染色f可得P(n，k)中各點(diǎn)的權(quán)重為：φ(ai)=10(i為奇數(shù))，φ(ai)=8(i為偶數(shù))，φ(bi)=8(i為奇數(shù))，φ(bi)=10(i為偶數(shù))．因bi總與bi+k相連，所以內(nèi)圈中的相鄰點(diǎn)下標(biāo)的奇偶性不同，則有φ(bi)=10(i為偶數(shù))≠φ(bi)=8(i為奇數(shù))，證畢．

引理2當(dāng)n為偶數(shù)，k為偶數(shù)時(shí)，fgndiΣ(P(n，k))≤3．

證根據(jù)不交圈的長(zhǎng)度p，分以下3種情形討論：

引理3當(dāng)n為奇數(shù)時(shí)，fgndiΣ(P(n，k))≤3．

情況2 對(duì)內(nèi)圈染色：令f(ai)=1，f(bi)=3．當(dāng)p?2(mod 3)時(shí)，令當(dāng)p≡2(mod 3)時(shí)，令

2 循環(huán)圖

由定義3知C(n，l)是正則圖，則fgndiΣ(C(n，l))≥2．定理2分以下4個(gè)引理證明：

引理4當(dāng)n為偶數(shù)，l為奇數(shù)時(shí)，fgndiΣ(C(n，l))=2．

證定義C(n，l)的一個(gè)2-全染色f如下：f(aiai+1)=f(aiai+l)=1，f(ai)=2(i≡1(mod 2))．由染色f可得C(n，l)中各點(diǎn)的權(quán)重為：φ(ai)=10(i≡0(mod 2))，φ(ai)=13(i≡1(mod 2))，證畢．

引理5當(dāng)n為奇數(shù)，l為偶數(shù)時(shí)，fgndiΣ(C(n，l))≤3．

引理7當(dāng)n=2l時(shí)，fgndiΣ(C(n，l))=2．

情形2 當(dāng)l=3時(shí)，令f(a1a4)=f(a3a4)=f(a4a5)=f(a4)=2，得φ(a1)=φ(a3)=φ(a5)=9，φ(a2)=φ(a6)=7，φ(a4)=11．

情形3 當(dāng)l=4時(shí)，令f(a1a5)=f(a3a7)=f(a3a4)=f(a4a5)=f(a5a6)=f(a5)=2，得φ(a1)=φ(a3)=φ(a6)=9，φ(a2)=φ(a8)=7，φ(a4)=10，φ(a5)=11，φ(a7)=8．

情形4 當(dāng)l=5時(shí)，令f(a1a6)=f(a3a8)=f(a4a9)=f(a2a3)=f(a5a6)=f(a6a7)=f(a9a10)=f(a4)=2，得φ(ai)=9(i=1，3，5，7，9)，φ(a2)=φ(a4)=φ(a8)=φ(a10)=8，φ(a6)=11．