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

李永艷, 杜 靜

(滄州交通學院 通識教育學院, 河北 黃驊 061199)

關(guān)于染色問題,國內(nèi)外許多學者在傳統(tǒng)邊染色、點染色和全染色基礎(chǔ)上,增加相應(yīng)的條件,提出了新的染色概念.Kalkowski M等[1]介紹了圖的鄰和可區(qū)別一般邊染色,Przybylo等[2]進一步提出鄰和可區(qū)別一般全染色概念,Flandrin等[3]在此基礎(chǔ)上提出鄰點擴展和可區(qū)別全染色,研究了路、圈、完全圖、樹等圖的鄰點擴展和可區(qū)別全染色,并提出一個猜想.張輝等[4-5]研究了星、扇、雙星及聯(lián)圖的鄰點擴展和可區(qū)別全染色.劉秀麗[6]討論了Mycielski圖的鄰點可區(qū)別I-全染色,本文研究了路、圈、星、扇、輪的Mycielski圖的鄰點擴展和可區(qū)別全染色.

1 預(yù)備知識

定義2[6]對簡單圖G,若V(M(G))=V(G)∪V′∪{ω},

其中:V′={v′|v∈V(G)},{ω}∩(V∪V′)=?,稱圖M(G)是圖G的Mycielski圖.

命題1[3]設(shè)Pm(m≥2)是m階的路,則

命題2[3]設(shè)Cm(m≥3)是m階的圈,則

egndi∑(Cm)=2

命題3[3]設(shè)Kn(n≥2)是n階的完全圖,則

egndi∑(Kn)=2

命題4[3]設(shè)T是n(n≥2)階的樹,則

egndi∑(T)≤2

猜想1(NESD猜想)[3]設(shè)G為簡單圖,則

egndi∑(G)≤2

文中未加說明的符號或術(shù)語可參見文獻[7].

2 主要結(jié)果

定理1設(shè)Pn表示階為n(n≥2)的路,則有egndi∑(M(Pn))=2.

證明設(shè)V(Pn)={v1,v2,…,vn},E(Pn)={v1v2,v2v3,…,vn-1vn},則

V(M(Pn))={v1,v2,…,vn}∪

{v′1,v′2,…,v′n}∪{ω}

E(M(Pn))={vivi+1|i=1,2,…,n-1}∪

{ωv′i|i=1,2,…,n}∪

{viv′j||i-j|=1,i,j=1,2,…,n}

令f是M(Pn)的一個全k-染色,顯然M(Pn)沒有NESD全1-染色,下面給出M(Pn)的一個NESD全2-染色.

情形1n=2.此時M(Pn)?C5,由命題2得

egndi∑(M(P2))=egndi∑(C5)=2

情形2n≥3.此時所有邊染顏色1,令f(ω)=1,f(vi)=1,i=1,2,…,n

則w(v′1)=w(v′n)=4,w(v′i)=6,i=2,3,…,n-1,w(v1)=4,

顯然,f是M(Pn)的一個NESD全2-染色.

定理2設(shè)Cn表示階為n(n≥3)的圈,則有

egndi∑(M(Cn))=2

證明M(Cn)即在M(Pn)的基礎(chǔ)上添加3條邊v1vn,v1v′n,v′1vn,

情形1n>3,n≡0(mod 4).此時M(Cn)與M(Pn)染色f相同,則w(v′i)=6,i=1,2,…,n,

顯然,f是M(Cn)的一個NESD全2-染色.

情形2n>3,n≡1(mod 4).此時在M(Pn)染色f基礎(chǔ)上,將f(vn-1vn)=1改為f(vn-1vn)=2,將f(v′n)=2改為f(v′n)=1 ,則w(v′i)=6,i=1,2,…,n

顯然,f是M(Cn)的一個NESD全2-染色.

情形3n>3,n≡2(mod 4).此時M(Cn)與M(Pn)染色f相同,則w(v′i)=6,i=1,2,…,n

顯然,f是M(Cn)的一個NESD全2-染色.

情形4n>3,n≡3(mod 4).此時在M(Pn)染色f基礎(chǔ)上,將f(v′n-1vn)=1改為f(v′n-1vn)=2,則w(v′i)=6,i=1,2,…,n-2,n,w(v′n-1)=7

顯然,f是M(Cn)的一個NESD全2-染色.

情形5n=3.此時設(shè)f是M(Cn)的一個全k-染色,令f(v′1)=2,其余點染顏色1,f(ωv′1)=f(v′2v3)=2,其余邊染顏色1,則w(v1)=w(ω)=8,w(v2)=9,w(v3)=10,w(v′1)=w(v′3)=6,w(v′2)=7.

顯然,f是M(C3)的一個NESD全2-染色.

定理3設(shè)Sn表示階為n+1(n≥3)的星,則有egndi∑(M(Sn))=2.

證明設(shè)V(Sn)={v0,v1,v2,…,vn},E(Sn)={v0vi|i=1,2,…,n},則

V(M(Sn))={v0,v1,v2,…,vn}∪

{v′0,v′1,v′2,…,v′n}∪{ω}

E(M(Sn))={v0vi|i=1,2,…,n}∪

{v0v′i|i=1,2,…,n}∪

{v′0vi|i=1,2,…,n} ∪

{ωv′i|i=0,1,2,…,n}

設(shè)f是M(Sn)的一個全k-染色,顯然M(Sn)沒有NESD全1-染色,下面給出M(Sn)的一個NESD全2-染色.

令f(v′0)=2,其余點和所有邊都染顏色1,則w(v0)=4n,w(vi)=5,i=1,2,…,n,w(v′0)=2n+2,w(v′i)=4,i=1,2,…,n,w(ω)=2n+3.

顯然,f是M(Sn)的一個NESD全2-染色.

定理4設(shè)Fn表示階為n+1(n≥3)的扇,則有egndi∑(M(Fn))=2.

證明M(Fn)即在M(Sn)的基礎(chǔ)上添加邊{vivi+1|i=1,2,…,n-1},{v′ivi+1|i=1,2,…,n-1},{v′ivi-1|i=2,…,n},設(shè)f是M(Fn)的一個全k-染色,顯然M(Fn)沒有NESD全1-染色,下面給出M(Fn)的一個NESD全2-染色.

情形1n≥3(n≠6).此時所有邊都染顏色1,令f(ω)=f(vi)=1,i=0,1,2,…,n

顯然,f是M(Fn)的一個NESD全2-染色.

情形2n=6.此時在情形1的染色f基礎(chǔ)上,將f(ωv′0)=1改為f(ωv′0)=2,則w(v′0)=14改為w(v′0)=15,w(ω)=16改為w(ω)=17.

顯然,f是M(F6)的一個NESD全2-染色.

定理5設(shè)Wn表示階為n+1(n≥3)的輪,則有egndi∑(M(Wn))=2.

證明M(Wn)即在M(Fn)的基礎(chǔ)上添加邊v1vn,v′1vn,v1v′n,

設(shè)f是M(Wn)的一個全k-染色,顯然M(Wn)沒有NESD全1-染色,下面給出M(Wn)的一個NESD全2-染色.

情形1n=3.此時令f(v′0)=f(v′2)=2,f(v0v1)=f(v1v3)=2,其余點和邊都染顏色1,則w(v0)=14,w(v1)=16,w(v2)=13,w(v3)=15,w(v′0)=w(v′1)=w(v′3)=8,w(v′2)=9,w(ω)=10.

顯然,f是M(W3)的一個NESD全2-染色.

情形2n>3且n≠6,n≡0,1,2(mod 4).此時令f(v0v1)=2,其余邊都染顏色1,f(ω)=f(vi)=1,i=0,1,2,…,n

顯然,f是M(Wn)的一個NESD全2-染色.

情形3n=6.此時在情形2的染色f基礎(chǔ)上,將f(ωv′0)=1改為f(ωv′0)=2,則w(v′0)=14改為w(v′0)=15,w(ω)=16改為w(ω)=17.

顯然,f是M(W6)的一個NESD全2-染色.

情形4n>3且n≡3(mod 4).此時在情形2的染色f基礎(chǔ)上,將f(v′n-1vn)=1改為f(v′n-1vn)=2,則w(v′n-1)=8改為w(v′n-1)=9.

顯然,f是M(Wn)的一個NESD全2-染色.

可以看出,猜想1對上述定理中的圖M(Pn)、M(Cn)、M(Sn)、M(Fn)、M(Wn)是成立的.