若干倍圖的2-距離和可區(qū)別全染色

王同昕，楊 超*，殷志祥，姚 兵

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

0 引言

猜想1[5]對階數(shù)至少為2的任意圖G，有tndiΣ(G)≤Δ(G)+3.

猜想1對稀疏圖[6]、無K4-子式圖[7]、最大度至少為13的平面圖[8]均成立.Cheng等[9]證明了最大度至少為14的平面圖鄰和可區(qū)別全色數(shù)不超過Δ(G)+2，進一步證實了猜想1；姚麗[10]將鄰和可區(qū)別全染色進行推廣，介紹了圖的2-距離和可區(qū)別全染色，得到了路、圈、星、扇、輪、完全二部圖的2-距離和可區(qū)別全色數(shù).受上述研究啟發(fā)，本文探討幾類倍圖的2-距離和可區(qū)別全染色問題.

1 預(yù)備知識

定義2[11]設(shè)G′是簡單圖G的一個拷貝，記G的頂點為ui，G′相對應(yīng)的頂點為vi.若圖G滿足下述條件：

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

(ii)E(D(G))=E(G)∪E(G′)∪{uivj:ui∈V(G),vj∈V(G′),uivj∈E(G)}，

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

路P4的倍圖D(P4)如圖1所示.

圖1 倍圖D(P4)

2 主要工作

定理1設(shè)Pn表示階為n(n≥4)的路，則

定義D(Pn)的一個6-全染色f如下:

由上述染色可得，S(u1)=6,S(v1)=12，這里S(u2),S(v2),…,S(un-1),S(vn-1)按照19,20,15,16,17,18循環(huán)，當(dāng)n≡0(mod3)時S(un)=6,S(vn)=13；當(dāng)n≡1(mod3)時S(vn)=7,S(un)=11；當(dāng)n≡2(mod3)時S(un)=12,S(vn)=13.故D(Pn)中2-距離點的權(quán)重可區(qū)別.】

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

倍圖D(C3)的一個 2-距離和可區(qū)別6-全染色如圖2所示.

圖2 倍圖D(C3)的一個2-距離和可區(qū)別6-全染色

接下來討論n≥4的情形.假設(shè)D(Cn)中存在一個6-全染色，則一共有6種全染色方案，而D(Cn)中與點u1距離小于等于2的點至少有7個，矛盾.故D(Cn)的一個正常全染色至少需要7種顏色.定義D(Cn)的一個7-全染色f如下：

情形1n=0(mod3).

由上述染色可得，S(u1)=21,S(V1)=18，這里S(u2),S(v2),S(u3),S(v3),…,S(un-1),S(vn-1)以19,20,15,16,17,18循環(huán)，S(un)=16,S(vn)=22.

情形2n=1(mod3).

由上述染色得，S(u1)=17,S(v1)=23，這里S(u2),S(v2),S(u3),S(v3),…,S(un-1),S(vn-1)以19,20,15,16,17,18循環(huán)，S(un)=18,S(vn)=22.

情形3n=2(mod3).

由上述染色可得，S(u1)=21,S(v1)=23，這里S(u2),S(v2),S(u3),S(v3),…,S(un-1),S(vn-1)以19,20,15,16,17,18循環(huán)，S(un)=27,S(vn)=22.

綜上所述，f為D(Cn)的一個2-距離和可區(qū)別7-全染色.】

根據(jù)上述染色可得D(Fn)各點權(quán)重如下：

由上述染色可得D(Wn)(n≠8)中各點權(quán)重為：

即f為D(Wn)(n≠8)的一個2-距離和可區(qū)別(2n+2)-全染色.

當(dāng)n=8時，上述染色方案中出現(xiàn)S(u1)=S(u2)=43的情況，此時用5重染點u1，得S(u1)=44≠S(u2)=43，由于其它點和邊的染色未改變，故可得W8的一個2-距離和可區(qū)別18-全染色.

綜上所述，定理得證.】

證明設(shè)

由上述染色可得，

即f為D(S2n)的一個2-距離和可區(qū)別(2n+4)-全染色.】

定理6設(shè)Km,n(3≤m≤n)為完全二部圖，則

證明 情形1m=n.

設(shè)V(Kn,n)={ui,vi:i=1,2,…,n},E(Kn,n)={uivj:i,j=1,2,…,n}.由引理1可得，

所以Kn，n的一個正常全染色至少需要n+3種顏色.下面構(gòu)造Kn，n的一個正常(n+3)-全染色f:

由上述染色，容易驗證：

故f為Kn，n的一個2-距離和可區(qū)別(n+3)-全染色.

情形2m

由上述染色可得：

故f為Km，n的一個2-距離和可區(qū)別(n+2)-全染色.】

由倍圖的定義可知，D(Km,n)=K2m,2n，星Sn的倍圖為完全二部圖K2，2n，故由定理6直接可得下述結(jié)論：

推論1設(shè)Km，n為完全二部圖，則