若干倍圖的鄰點全和可區(qū)別全染色

程銀萬, 楊 超*, 姚 兵

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

圖染色問題是圖論中經(jīng)典問題之一,其研究成果已被廣泛應用于通信網(wǎng)絡、控制論、計算機科學與編碼理論等領域.由于應用的廣泛性,許多學者在傳統(tǒng)染色的基礎上陸續(xù)提出了一系列新染色.2004年,Karoński等提出了圖的鄰和可區(qū)別邊染色的概念,并給出了該染色下的1-2-3猜想[1].2021年,Przybylo證明了每個d-正則圖(d≥2)都是鄰和可區(qū)別4-邊染色的,且當d≥108時,每個d-正則圖是鄰和可區(qū)別3-邊染色的[2].2010年,Przybylo和Wozniak將頂點自身的顏色加入其關聯(lián)邊的顏色和中,定義了圖的鄰和可區(qū)別全染色,同時給出了基于鄰和可區(qū)別全染色的1-2猜想[3].目前,一個較為理想的結果是:任意圖的鄰和可區(qū)別全色數(shù)不超過3[4].2017年,Flandrin等在鄰和可區(qū)別全染色的基礎上,將任意一點的所有鄰點顏色加入其全染色權重和中,提出了圖的鄰點全和可區(qū)別全染色的概念[5].注意到,Flandrin等在文獻[5]中僅將圖的鄰點全和可區(qū)別全染色與鄰點被擴展和可區(qū)別全染色作了一個簡單的對比,并未進行深入研究.近年來,圖的鄰點全和可區(qū)別全染色在文獻[6-7]中被進一步研究.受此啟發(fā),本文研究路、圈、星、扇、輪、完全二部圖以及樹的倍圖的鄰點全和可區(qū)別全染色問題．

1 預備知識

本文涉及的圖均為連通的簡單圖,V(G)和E(G)分別表示圖G的點集和邊集,d(v)表示圖中頂點v的度.文中未定義的術語和符號均參考文獻[8].下面先介紹與本文有關的定義和概念．

定義1[5]設f：V(G)∪E(G)→[1,k]是圖G的一個k-全染色.定義頂點x的權重函數(shù):

(1)

其中,N(x)={y∈V(G)│xy∈E(G)}.對于任意邊uv∈E(G),若有φ(u)≠φ(v)成立,則稱f是圖G的一個鄰點全和可區(qū)別k-全染色(簡記NFSD).圖G的鄰點全和可區(qū)別全染色中最小的k值稱為G的鄰點全和可區(qū)別全色數(shù),記為fgndiΣ(G)．

定義2[9]設G′是簡單圖G的拷貝,記G的頂點為ui,G′相應的頂點為vi,若圖D(G)滿足:

1)V(D(G))=V(G)∪V(G′);

2)E(D(G))=E(G)∪E(G′)∪{uivj│ui∈V(G),vj∈V(G′),uiuj∈E(G)},

則稱D(G)為G的倍圖．

當n=3時,路P3的倍圖D(P3)如圖1所示.

圖1 倍圖D(P3)Fig.1 Double graph D(P3)

2 主要結論及證明

定理1若圖G中存在度相同的相鄰點,則fgndiΣ(G)≥2．

證明(反證法)假設圖G中存在度相同的相鄰點u,v,即d(u)=d(v).若圖G中的點和邊均染顏色1,則由公式(1)得φ(u)=φ(v)=2d(u)+1=2d(v)+1,與定義1相矛盾,故fgndiΣ(G)≥2．

定理2設Pn=u1u2u3…un表示n(n≥1)階的路,當n=1,3時,fgndiΣ(D(Pn))=1;其他情形,fgndiΣ(D(Pn))=2.

證明由定義2知,當n=1,3時,圖D(Pn)中不存在度相同的相鄰點,所以,當D(Pn)中所有點和邊都染顏色1時,不存在相鄰點權重相同的情況,符合定義1.當n≠1,3時,由定理1知,至少需要2種顏色才可以完成對圖D(Pn)的鄰點全和可區(qū)別全染色.下面給出對圖D(Pn)的點和邊的具體染色．

定義D(Pn)的一個全染色f1：V(D(Pn))∪E(D(Pn))→[1,2]如下:

f1(ui)=f1(vi)=1,1≤i≤n,ui,vi∈V(D(Pn));

f1(e)=2,其中,e∈{uiui+1│i≡1,2(mod 4)}∪{vivi+1│i≡0,3(mod 4)};

f1(e0)=1,e0∈E(D(Pn)){e}．

染色f1代入公式(1),可得圖D(Pn)中各點的權重如下.

情形1n≡0(mod 4).

情形2n≡1(mod 4).

情形3n≡2(mod 4).

情形4n≡3(mod 4).

因為各相鄰點權重不同,所以f1為D(Pn)的一個NFSD-2-全染色.

定理3設Cn=u1u2u3…unu1表示階數(shù)為n(n≥3)的圈,則fgndiΣ(D(Cn))=2．

證明根據(jù)定理1,由于圖D(Cn)中存在度相同的相鄰點,所以至少需要2種顏色才能完成對D(Cn)的鄰點全和可區(qū)別全染色.下面分4種情形對D(Cn)的點和邊進行染色．

情形1n≡0(mod 4).

定義D(Cn)的一個全染色f2：V(D(Cn))∪E(D(Cn))→[1,2]如下:

f2(ui)=f2(vi)=1,1≤i≤n,ui,vi∈V(D(Cn));

f2(e)=2,e∈{uiui+1,vivi+1│i≡2,3(mod 4)};

f2(e0)=1,e0∈E(D(Cn)){e}．

由染色f2可得圖D(Cn)中各點的權重如下:

情形2n≡1(mod 4).

定義D(Cn)的一個全染色f3：V(D(Cn))∪E(D(Cn))→[1,2]如下:

ui,vi∈V(D(Cn));f3(e)=2,e∈{uiui+1,vivi+1│i≡1,2(mod 4),i≠1};f3(e0)=1,e0∈E(D(Cn)){e}．

由染色f3可得圖D(Cn)中各點的權重如下:

情形3n≡2(mod 4).

定義D(Cn)的一個全染色f4：V(D(Cn))∪E(D(Cn))→[1,2]如下:

1≤i≤n,ui,vi∈V(D(Cn));f4(e)=2,e∈{uiui+1,vivi+1│i≡0,3(mod 4)};f4(e0)=1,e0∈E(D(Cn)){e}．

由染色f4可得圖D(Cn)中各點的權重如下:

情形4n≡3(mod 4).

定義D(Cn)的一個全染色f5：V(D(Cn))∪E(D(Cn))→[1,2]如下:

ui,vi∈V(D(Cn));f5(e)=2,e∈{uiui+1,vivi+1│i≡0,1(mod 4),i≠1};f5(e0)=1,e0∈E(D(Cn)){e}．

由染色f5可得圖D(Cn)中各點的權重如下:

因為各相鄰點權重不同,所以f2,f3,f4,f5分別為各情形下D(Cn)的一個NFSD-2-全染色.

定理4設Sn表示階數(shù)為n+1(n≥3)的星,則fgndiΣ(D(Sn))=1．

證明設Sn的點集和邊集分別為:V(Sn)={u1,u2,…,un+1},E(Sn)={uiun+1│1≤i≤n}.由定義2知,圖D(Sn)為完全二部圖,即D(Sn)=K2,2n.根據(jù)定理1,圖D(Sn)中不存在度相同的相鄰點,所以只需要一種顏色就可以完成圖D(Sn)的鄰點全和可區(qū)別全染色,即fgndiΣ(D(Sn))=1．

定理5設Fn表示階數(shù)為n+1(n≥3)的扇,則fgndiΣ(D(Fn))=2．

證明設Fn的點集和邊集分別為:V(Fn)={u1,u2,…,un+1},E(Fn)={uiun+1│1≤i≤n}∪{uiui+1│1≤i≤n-1}.由定義2知,圖Fn中存在度相同的相鄰點,所以至少需要兩種顏色才可以完成Fn的鄰點全和可區(qū)別全染色.具體全染色方案f6：V(D(Fn))∪E(D(Fn))→[1,2]如下:

f6(ui)=f6(vi)=1,1≤i≤n+1;f6(e)=2,e∈{uiui+1,vivi+1│i≡0,1(mod 4)};f6(e0)=1,e0∈E(D(Fn)){e}．

由染色f6可得如下三種情形圖Fn中各點的權重．

情形1n≡0,3(mod 4).

情形2n≡1(mod 4).

情形3n≡2(mod 4).

因為各情形下相鄰點權重不同,所以f6為D(Cn)的一個NFSD-2-全染色．

定理6設Wn表示階數(shù)為n+1(n≥3)的輪,則fgndiΣ(D(Wn))=2．

證明設Wn的點集和邊集分別為:V(Wn)={u1,u2,…,un+1},E(Wn)={uiun+1│1≤i≤n}∪{uiui+1│1≤i≤n-1}∪{unu1}.以下分兩種情形證明．

情形1n=3.

定義染色f7：V(D(Wn))∪E(D(Wn))→[1,2]如下:

f7(vi)=1,1≤i≤n+1;f7(e)=2,e∈{u1u2,u1v2,u1v4,u2v4,u3v4,v2v4,v3v4};f7(e0)=1,e0∈E(D(Wn)){e}．

由染色f7可得各點權重如下:

φ(u1)=17,φ(u2)=16,φ(u3)=15,φ(u4)=14,φ(v1)=13,φ(v2)=16,φ(v3)=15,φ(v4)=19．

因為相鄰點權重不同,所以f7為D(W3)的一個NFSD-2-全染色．

情形2n≥4.

1)當n≡0(mod 4)時,定義染色f8：V(D(Wn))∪E(D(Wn))→[1,2]如下:

f(ui)=f(vi)=1,1≤i≤n+1;

f(e)=2,e∈{uiui+1,vivi+1│i≡2,3(mod 4)};

f(e0)=1,e0∈E(D(Cn)){e}．

由染色f8可得各點權重如下:

2)當n≡1(mod 4)時,定義染色f9：V(D(Wn))∪E(D(Wn))→[1,2]如下:

f9(e)=2,e∈{uiui+1,vivi+1│i≡1,2(mod 4),i≠1};f9(e0)=1,e0∈E(D(Wn)){e}．

由染色f9可得各點權重如下:

3)當n≡2(mod 4)時,定義染色f10：V(D(Wn))∪E(D(Wn))→[1,2]如下:

f10(e)=2,e∈{uiui+1,vivi+1│i≡0,3(mod 4)};f10(e0)=1,e0∈E(D(Wn)){e}．

由染色f10可得各點權重如下:

4)當n≡3(mod 4) 時,定義染色f11：V(D(Wn))∪E(D(Wn))→[1,2]如下:

1≤i≤n+1;f11(e)=2,e∈{uiui+1,vivi+1│i≡0,1(mod 4),i≠1};f11(e0)=1,e0∈E(D(Wn)){e}．

由染色f11可得各點權重如下:

因為各情形下相鄰點權重不同,所以f8、f9、f10、f11分別為各情形下D(Cn)的一個NFSD-2-全染色．

定理7設Km,n(m≥1,n≥1)表示完全二部圖,則fgndiΣ(D(Km,n))=2(m=n);fgndiΣ(D(Km,n))=1(m≠n).

證明令V(Km,n)=X∪Y,E(Km,n)={uivj│1≤i≤m,1≤j≤n},其中X={u1,u2,…,um},Y={v1,v2,…,vn}.首先,完成對完全二部圖的鄰點全和可區(qū)別全染色,其次,通過倍圖的連接特征發(fā)現(xiàn),完全二部圖Km,n的倍圖D(Km,n)即為完全二部圖K2m,2n.下面分兩種情形證明．

情形1m=n．

定義染色f12：V(Km,n)∪E(Km, n)→[1,2]如下:

f12(ui)=1,f12(vi)=2,f12(uivj)=1,1≤i≤m,1≤j≤n．

由上述染色f12可得各點權重如下:

φ(ui)=3m+1,φ(vi)=2m+2.

觀察發(fā)現(xiàn),僅當m=1時,φ(ui)=φ(vi),而其倍圖K2m,2n的點集X、Y的階數(shù)均大于等于2,故對于圖K2m,2n,φ(ui)≠φ(vi)恒成立．

情形2m≠n.

定義染色f13：V(Km,n)∪E(Km,n)→[1,2]如下:

f13(ui)=f13(vi)=f13(uivj)=1,1≤i≤m,1≤j≤n.

由染色f13可知,φ(ui)=2n+1,φ(vi)=2m+1.

所以,此情形下,φ(ui)≠φ(vi)恒成立．

上述兩種情形表明完全二部圖Km,n的鄰點全和可區(qū)別全色數(shù)是確定的.由于Km,n的倍圖D(Km,n)也是完全二部圖,所以f12和f13分別是各情形下的一種NFSD-全染色．

定理8設T表示n(n≥3)階樹.若樹T中不存在度相同的相鄰點,則fgndiΣ(D(T))=1;若樹T中存在度相同的相鄰點,則fgndiΣ(D(T))=2.

證明當樹T中不存在度相同的相鄰點時,樹的倍圖中也不存在度相同的相鄰點,根據(jù)定理1,僅需1種顏色就可以完成樹倍圖的鄰點全和可區(qū)別全染色.下面討論樹中存在度相同的相鄰點情形,首先通過構建樹染色算法完成樹的鄰點全和可區(qū)別全染色;其次結合樹倍圖的結構特點進行分析證明.樹的鄰點全和可區(qū)別全染色算法如下.

步驟1樹T中每個頂點染顏色1．

步驟2對樹T中邊的染色定義如下兩種染色方式.

f14(eu):對頂點u的所有未染色的鄰邊分配顏色2;

f15(eu):對頂點u的一條未染色的鄰邊分配顏色1,其余鄰邊染顏色2．

步驟3選擇樹T中任一度數(shù)為奇數(shù)的頂點,記為u.即d(u)≡1(mod 2).對u的鄰邊選擇染色方式f14(eu)．

步驟4設ui為點u的鄰點．

當d(ui)≡1(mod 2)時,采用染色方式f15(eui);

當d(ui)≡0(mod 2)時,采用染色方式f14(eui)．

步驟5設uij為點ui的鄰點．當d(ui)≡0(mod 2)時,

若d(uij)≡1(mod 2),采用染色f14(euij);

若d(uij)≡0(mod 2),采用染色f15(euij)．

當d(ui)≡1(mod 2)且f(uiuij)=2時,

若d(uij)≡1(mod 2),采用染色方式f14(euij);

若d(uij)≡0(mod 2),采用染色方式f15(euij)．

當d(ui)≡1(mod 2)且f(uiuij)=1時,

若d(uij)≡1(mod 2),采用染色方式f15(euij);

若d(uij)≡0(mod 2),采用染色方式f14(euij)．

步驟6設uijk為點uij的鄰點．當d(ui)≡1(mod 2)且d(uij)≡1(mod 2)且f(uijuijk)=1時,

若d(uijk)≡0(mod 2),采用染色方式f15(euijk);

若d(uijk)≡1(mod 2),采用染色方式f14(euijk)．

當d(ui)≡1(mod 2)且d(uij)≡1(mod 2)且f(uijuijk)=2時,

若d(uijk)≡0(mod 2),采用染色方式f14(euijk);

若d(uijk)≡1(mod 2),采用染色方式f15(euijk)．

其他情況下的邊染色依照步驟5．

步驟7繼續(xù)上述過程,直至樹T的邊都被染了顏色1或2．

完成上述的樹染色過程,樹中相鄰頂點的權重是奇偶可分的,即相鄰點的權重不同.假設樹T′是樹T的復制,其染色方式和樹T保持一致,且樹T和T′之間的連線都染顏色1,觀察樹倍圖的結構發(fā)現(xiàn),此時D(T)中頂點的權重均增加了2d(u)+1,由于2d(u)+1是奇數(shù),所以樹T和T′中的頂點權重的奇偶性均發(fā)生了變化.但是,D(T)中相鄰點的權重依然是奇偶可分的,即相鄰點權重不同.假設樹T中的葉子節(jié)點為vi,那么染色后圖D(T)中φ(vi)≤6,而與vi相鄰的次結點的權重大于等于9,所以葉子結點的權重小于內(nèi)點權重恒成立.綜上所述,兩種顏色可以完成D(T)的鄰點全和可區(qū)別全染色．