平方圖的鄰點全和可區(qū)別全染色

王 芹, 楊 超*, 常景智, 程銀萬, 姚 兵

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

圖的染色理論在離散系統(tǒng)、組合分析和網(wǎng)絡(luò)通訊等領(lǐng)域有著廣泛的應(yīng)用,具體涉及時間表問題、排序問題、排課表問題、存儲問題、電路安排和任務(wù)分配等。由于其重要的理論意義和廣泛的應(yīng)用價值,染色問題一直是學(xué)者們關(guān)注和研究的熱點。

在圖的鄰點被擴(kuò)展和可區(qū)別全染色的基礎(chǔ)上, FLANDRIN等[11]進(jìn)一步定義了圖的鄰點全和可區(qū)別非正常全染色,但并未對圖的鄰點全和可區(qū)別非正常全染色問題進(jìn)行深入探究,僅僅把圖的鄰點全和可區(qū)別非正常全染色與鄰點被擴(kuò)展和可區(qū)別全染色作了一個簡單的比較。基于此,本文將深入探討路、圈、毛毛蟲、廣義星以及最大度為 3 且不包含 2 度點的樹的平方圖的鄰點全和可區(qū)別非正常全染色問題。

1 預(yù)備知識

本文論及的圖G均為無向簡單圖,用V(G)、E(G)分別表示G的頂點集、邊集。符號[s,t]表示非負(fù)整數(shù)集{s,s+1,s+2,…,t},其中s和t均為整數(shù),且滿足0≤s

設(shè)u、v為圖G中任意兩點,distG(u,v)表示連接u、v兩點間的最短路的長度。圖G的平方圖G2是以V(G)作為它的點集,2個點u、v在G2中相鄰當(dāng)且僅當(dāng)1≤distG(u,v)≤2。圈C6的平方圖如圖1所示。容易驗證,星、輪和完全r-部圖(r≥2)的平方圖均為完全圖。

圖1 圈C6的平方圖

下面給出 2 類特殊樹的定義。

定義2設(shè)圖G的點集V(G)={v0,vn+1,vi,v′i,v″i|i[1,n]}, 邊集E(G)={viv′i,viv″i,vivi+1,v0v1|i[1,n]},則稱圖G為毛毛蟲。

毛毛蟲示意圖見圖 2。由定義 2 知,dG(v0)=dG(v′i)=dG(v″i)=dG(vn+1)=1,dG(vi)=4,i[1,n]。當(dāng)n=1時,|G|=5,此時毛毛蟲G的平方圖是完全圖K5,即G2=K5。

圖2 毛毛蟲

定義3設(shè)圖S的點集V(S)={v0,vi,j|i[1,n],j[1,h]},邊集E(S)={v0vi,1,vi,j-1vi,j|i[1,n],j[2,h]},則稱圖S為廣義星(圖3)。

圖3 廣義星

2 主要結(jié)果

f1(v4i-4v4i-3)=1,f1(v4i-3v4i-2)=1,f1(v4i-2v4i-1)=1,f1(v4i-1v4i)=2,i[1,n];f1(v2 iv2 i+2)=1,f1(v2 i+1v2 i+3)=2,i[0,n]。

由染色f1可得：φ(v4i)=10,φ(v4 i+1)=11,φ(v4 i+2)=9,φ(v4i+3)=12,i[0,n]。則f1為的一個鄰和可區(qū)別非正常 2- 邊染色。

f2(v0v1)=f2(v4v5)=1,f2(v1v2)=f2(v2v3)=f2(v3v4)=f2(v5v6)=f2(v6v7)=2;f2(v4i-1v4i)=f2(v4iv4i+1)=f2(v4i+1v4i+2)=1,f2(v4i+2v4i+3)=2,i[2,n];f2(v0v2)=1,f2(v1v3)=2,f2(v2v4)=1,f2(v3v5)=2,f2(v4v6)=f2(v5v7)=1,f2(v6v8)=2;f2(v2i-1v2i+1)=1,f2(v2iv2i+2)=2,i[4,n]。

由染色f2可得:φ(v0)=9,φ(v1)=12,φ(v2)=11,φ(v3)=13,φ(v4)=10,φ(v5)=11,φ(v6)=12,φ(v7)=10,φ(v8)=11,φ(v4i-3)=9,φ(v4i-2)=12,φ(v4i-1)=10,φ(v4i)=11,i[3,n]。則f2為的一個鄰和可區(qū)別非正常2-邊染色。

f3(v4 iv4 i+1)=f3(v4 i+1v4 i+2)=f3(v4 i+2v4 i+3)=1,f3(v4 i+3v4 i+4)=

f3(vn-2vn-1)=2,f3(vn-1v0)=2,f3(v2 iv2 i+2)=1,f3(v2 i+1v2 i+3)=2,i[0,n]。

由染色f3可得:φ(v4 i)=10,φ(v4 i+1)=11,φ(v4 i+2)=9,φ(v4 i+3)=12,φ(vn-2)=11,φ(vn-1)=13,i[0,n]。則f3為的一個鄰和可區(qū)別非正常 2-邊染色。

f4(v0v1)=1,f4(v1v2)=f4(v3v4)=2,f4(v2v3)=1;f4(v4iv4i+1)=2,f4(v4i+1v4i+2)=f4(v4i+2v4i+3)=f4(v4i+3v4i+4)=1,i[1,n];f4(v0v2)=f4(v2v4)=1,f4(v1v3)=2;f4(v2i-1v2i+1)=1,f4(v2iv2i+2)=2,i[2,n]。

由染色f4可得:φ(v0)=9,φ(v1)=12,φ(v2)=10,φ(v3)=11,φ(v4)=12,φ(v5)=10,φ(v6)=11,φ(v4i-1)=9,φ(v4i)=12,φ(v4i+1)=10,φ(v4i+2)=11,i[2,n]。則f4為的一個鄰和可區(qū)別非正常 2-邊染色。

f1(v0v1)=1,f1(v1v2)=2,f1(v0v2)=1;f1(v3i-1v3i)=f1(v3 iv3 i+1)=2,f1(v3 i+1v3 i+2)=f1(v3 i-1v3 i+1)= 1,f1(v3 iv3 i+2)=2,f1(v3 i-2v3 i)=1,i[1,n]。

由染色f1可得:φ(v0)=5,φ(v1)=8,φ(v3 i+1)=10,φ(v3i-1)=11,φ(v3i)=12,φ(vn-2)=8,φ(vn-1)=6,i[1,n]。 則f1為的一個鄰和可區(qū)別非正常 2-邊染色。

f2(v0v1)=1,f2(v1v2)=2,f2(v0v2)=1,f2(v3i-1v3i)=f2(v3 iv3 i+1)=2,f2(v3 i+1v3 i+2)=f2(v3 i-1v3 i+1)=1,f2(v3iv3i+2)=2,f2(v3i-2v3i)=f2(vn-2vn-1)=1,i[1,n]。

由染色f2可得:φ(v0)=5,φ(v1)=8,φ(v3i+1)=10,φ(v3i-1)=11,φ(v3i)=12,φ(vn-2)=8,φ(vn-1)=5,i[1,n],則f2為的一個鄰和可區(qū)別非正常2-邊染色。

定理3設(shè)G為階數(shù)為n的毛毛蟲。若n=5, 則 fgndi∑(G2)=3;若n>5,則 fgndi∑(G2)=2。

證明設(shè)G為階數(shù)為n的毛毛蟲,G2如圖 4 所示。若n=5,則G2=K5，容易驗證fgndi∑(G2)=fgndi∑(K5)=3。以下考慮n>5的情形。由定義2知,dG2(v0)=dG2(vn+1)=dG2(v′i)=dG2(v″i)=4,dG2(v1)=dG2(vn)=7,dG2(vi)=10,i[2,n-1]。若G2的所有點和邊均染顏色 1,則φ(v0)=φ(vn+1)=φ(v′i)=φ(v″i)=9,φ(v1)=φ(vn)=15,φ(vi)=21,i[2,n-1],矛盾。故G2的一個鄰和可區(qū)別非正常全染色至少需 2 種顏色,不妨用顏色 1 和顏色 2 對G2進(jìn)行非正常全染色且頂點全部染顏色 1。則φ(v0)、φ(vn+1)、φ(v′i)、φ(v″i)均不超過13,且φ(v1),φ(vn)≥15, 但φ(vi)≥21,i[2,n]。故φ(vi){φ(v0),φ(vn+1),φ(v′i),φ(v″i),φ(v1),φ(vn)}。 故按上述染色方案,若要證G2存在一個鄰和可區(qū)別非正常2-全染色,則僅需證G2存在一個鄰和可區(qū)別非正常 2-邊染色。

圖4 毛毛蟲的平方圖

下面分2種情況對G2的邊進(jìn)行染色。

情形1.n≡0(mod 3)。定義G2的一個2-邊染色f1如下:

f1(v″3i-2v3i-1)=f1(v″3i-1v3i)=1,f1(v″3iv3i+1)=2,i[1,n],

剩余其他邊全部染顏色1。

由染色f1可得,φ(v0)=10,φ(v1)=17,φ(v3i-1)=22,φ(v3i)=23,φ(v3i+1)=24,φ(vn)=16,φ(vn+1)=10,φ(v′i)=9,φ(v″i)=11,則f1為G2的一個鄰和可區(qū)別非正常 2-邊染色。

f2(v″3iv3i+1)=f2(v″nvn+1)=2,i[1,n],

其余邊全部染顏色1。

由染色f2可得,φ(v0)=10,φ(v1)=17,φ(v3i-1)=22,φ(v3i)=23,φ(v3i+1)=24,φ(vn)=15,φ(vn+1)=10,φ(v″i)=11,φ(v′i)=9,則f2為G2的一個鄰和可區(qū)別非正常 2-邊染色。

定理4設(shè)S是廣義星,則fgndi∑(S2)=2。

證明設(shè)S1,n=(V(S1,n),E(S1,n))為一個星,其中，V(S1,n)={v0,vi,1|i[1,n]},E(S1,n)={v0vi,1,v0vi,2|i[1,n]}。為敘述方便,稱S1,n為廣義星平方圖S2中的一個星結(jié)構(gòu)。設(shè)v0連接n條長為h的路,它們的點集記為{vi,1,vi,2,vi,3,…,vi,h|i[1,n]},邊集記為{vi,1vi,2,vi,2vi,3,vi,3vi,4,…,vi,h-1vi,h,vi,1vi,3,vi,2vi,4,vi,3vi,5,…,vi,h-2vi,h|i[1,n]}。

廣義星平方圖S2如圖 5 所示。下面對星結(jié)構(gòu)進(jìn)行染色。將星結(jié)構(gòu)分為 2 個部分:下標(biāo)i[1,「(n-1/2)?]的部分記為A,下標(biāo)i[「(n-1/2)?+1,n]的部分記為B。令與v0相連的邊全部染顏色2,則φ(v0)=6n+1。令f(vi,1vn,1)=1,i[1,n-1];f(vi,1vn-1,1)=1,i[2,n-2];f(vi,1vn-2,1)=1,i在A中令f(vi,1vi,2)=2(i[1,「(n-1)/2?]),在B中令f(vi,1vi,2)=1(i[「(n-1)/2?+1,n]),則星結(jié)構(gòu)上點的權(quán)重從vi,1開始以公差為1逐漸遞減,且權(quán)重區(qū)間為[3n+6,2n+7]。

圖5 廣義星的平方圖

下面對A中的路PA進(jìn)行染色。

情形 1.h≡0(mod 3)。定義PA的一個2-邊染色f1如下:

f1(vi,2vi,3)=f1(vi,h-1vi,h)=1;f1(vi,3 j-1vi,3 j)=2,j[2,h];

f1(vi,3jvi,3j+1)=f1(vi,3jvi,3j+2)=f1(vi,3j+1vi,3j+3)=1,

f1(vi,3j-1vi,3j+1)=f1(vi,3j+1vi,3j+2)=2,j[1,h]。

由染色f1可得:φ(vi,3j-1)=12,φ(vi,3j)=10,φ(vi,3j+1)=11；φ(vi,h-1)=8,φ(vi,h)=5,j[1,h]。則f1為S2的一個鄰和可區(qū)別非正常 2- 邊染色。

情形 2.h≡2(mod 3)。定義PA的一個2-邊染色f2如下:

f2(vi,2vi,3)=f2(vi,h-1vi,h)=f2(vi,h-2vi,h)=1,f2(vi,2vi,4)=2;f2(vi,3jvi,3j+1)=f2(vi,3jvi,3j+2)=f2(vi,3j+1vi,3j+3)=1,f2(vi,3j+1vi,3j+2)=f2(vi,3j+2vi,3j+3)=f2(vi,3j+2vi,3j+4)=2,j[1,h]。

由染色f2可得:φ(vi,3j-1)=12,φ(vi,3j)=10,φ(vi,3j+1)=11,φ(vi,h-1)=8,φ(vi,h)=5,j[1,h]。則f2為S2的一個鄰和可區(qū)別非正常 2- 邊染色。

情形 3.h≡1(mod 3)。定義PA的一個2-邊染色f3如下:

f3(vi,2vi,3)=1,f3(vi,2vi,4)=2;f3(vi,3 j-1vi,3 j)=2,j[2,h];f3(vi,3jvi,3j+1)=f3(vi,3jvi,3j+2)=f3(vi,3j+1vi,3j+3)=1,f3(vi,3 j-2vi,3 j-1)=2,j[2,h];f3(vi,3 j+2vi,3 j+4)=2,j[1,h]。

由染色f3可得:φ(vi,3 j-1)=12,φ(vi,3 j)=10,φ(vi,3 j+1)=11,φ(vi,n-1)=8,φ(vi,n)=6,j[1,h]。則f3為S2的一個鄰和可區(qū)別非正常 2- 邊染色。

下面對B中的路PB進(jìn)行染色。

情形 1.h≡0(mod 3)。定義PB的一個2-邊染色g1如下:

g1(vi,2vi,3)=g1(vi,3vi,4)=g1(vi,3vi,5)=2,g1(vi,4vi,5)=g1(vi,h-1vi,h)=1;g1(vi,3jvi,3j+1)=g1(vi,3jvi,3j+2)=1,g1(vi,3 j+1vi,3 j+2)=2,j[2,h];g1(vi,3 j-1vi,3 j)=g1(vi,3 j-1vi,3 j+1)=2,g1(vi,3j+1vi,3j+3)=1,j[1,h]。

由染色g1可得：φ(vi,2)=12,φ(vi,3)=13,φ(vi,4)=11,φ(vi,3j-1)=12,φ(vi,3j)=10,φ(vi,3j+1)=11,φ(vi,h-1)=8,φ(vi,h)=5,j[2,h]。則g1為S2的一個鄰和可區(qū)別非正常 2- 邊染色。

情形 2.h≡2(mod 3)。定義PB的一個2-邊染色g2如下:

g2(vi,2vi,3)=g2(vi,3vi,4)=g2(vi,3vi,5)=2,g2(vi,4vi,5)=1,g2(vi,h-1vi,h)=1;g2(vi,3j-1vi,3j)=g2(vi,3j-1vi,3j+1)=2,g2(vi,3 j-2vi,3 j)=1,j[1,h];g2(vi,3 jvi,3 j+1)=g2(vi,3 jvi,3 j+2)=1,g2(vi,3j+1vi,3j+2)=2,j[2,h]。

由染色g2可得：φ(vi,2)=12,φ(vi,3)=13,φ(vi,4)=11;φ(vi,3j-1)=12,φ(vi,3j)=10,j[2,h];φ(vi,3j+1)=11,φ(vi,h-1)=8,φ(vi,h)=5,j[2,h]。則g2為S2的一個鄰和可區(qū)別非正常 2- 邊染色。

情形 3.h≡1(mod 3)。定義PB的一個2-邊染色g3如下:

g3(vi,2vi,3)=g3(vi,3vi,4)=2,g3(vi,4vi,5)=1,g3(vi,2vi,4)=g3(vi,3vi,5)=2;g3(vi,3 jvi,3 j+1)=g3(vi,3 jvi,3 j+2)=1,g3(vi,3 j+1vi,3 j+2)=2,j[2,h];g3(vi,3 j+2vi,3 j+3)=g3(vi,3 j+2vi,3 j+4) = 2;g3(vi,3 j+1vi,3 j+3)=1,j[1,h]。

由染色g3可得:φ(vi,2)=12,φ(vi,3)=13,φ(vi,4)=11,φ(vi,3j-1)=12,φ(vi,3j)=10,φ(vi,3j+1)=11,φ(vi,h-1)=8,φ(vi,h)=6,j[2,h]。則g3為S2的一個鄰和可區(qū)別非正常 2-邊染色。

基于染色fi和gi(i[1,3])可得,廣義星平方圖S2中存在一個鄰點全和可區(qū)別非正常2-全染色。

定理5設(shè)D為最大度為3的樹且D中無2度點。若D2=K4,則fgndi∑(D2)=3;若D2≠K4,則fgndi∑(D2)=2。

接下來考慮D2的染色。由樹D的構(gòu)造過程知, 當(dāng)樹D每遞歸一次,D2中對應(yīng)增加 2 個新點和 5 條新邊。首先把連接2個 3 度點的那條新邊和2個新點都染顏色1,其余4條新邊記為e1、e2、e3、e4(具體對應(yīng)邊如圖6所示),(f(e1),f(e2),f(e3),f(e4))可能的染色方案(EC)如下:(C1)(1,2,1,1);(C2)(2,2,1,1);(C3)(2,2,1,2);(C4)(1,1,1,2)。按上述染色方案,要證D2存在一個鄰和可區(qū)別非正常 2-全染色,僅需證D2存在一個鄰和可區(qū)別非正常2-邊染色。通過對樹平方圖D2的3度點w進(jìn)行加點加邊處理,點w的度由原來的3度增加為5度,與點w相鄰的5度點則增加為7度點，與點w相鄰的7度點則變?yōu)?度點。不妨記vm、vn、vs、vt分別表示度為3、5、7、9的點。按照上述染色方案(EC),得φ(vt)[19,26],φ(vs)[15,20],則φ(vn)max=14 <φ(vs)min=15。因為樹平方圖中最多有4個度為 9 的點相鄰,所以可取φ(vt)[21,24],則φ(vs)max=20<φ(vt)min=21。通過上述討論,度不相同時相鄰點的權(quán)重也不相同。若存在 3 個度為 7 的點相鄰,由前面染色知,φ(vn)[11,14],φ(vs)[15,20]。根據(jù)染色方案(EC),總能找到 3 個不同權(quán)重來區(qū)分度為 7 的相鄰點。對于度為 9 的相鄰頂點,因為φ(vt)[21,24],所以總能在C1～C4中找到一種令這 4 個相鄰的9度點的權(quán)重不同的邊染色。

圖6 樹D2的構(gòu)造示意圖