廣義Mycielski圖Mn(Pt)的鄰點可區(qū)別的I-均勻全染色

張 婷，張修雪，王 昕，趙慧霞

(1.蘭州文理學院 教育學院, 甘肅 蘭州 730010 2.蘭州文理學院 學報編輯部, 甘肅 蘭州 730010)

圖的染色問題是圖論中的一個經(jīng)典而古老的問題，也是圖論領(lǐng)域的一個重要研究方向.目前,圖的染色問題已由傳統(tǒng)的點染色、邊染色、全染色拓展為各類具有復雜特征的新型染色問題,圖的均勻染色就是其中之一.圖的均勻染色強調(diào)了任意兩個色類所染元素個數(shù)最大相差為1,它常用來解決一些分配、調(diào)度及負載平衡問題.1973年, Meyer[1]最早提出了均勻染色的概念;1994年, Fu H[2]在《Some results on equalized total coloring》中提出了均勻全染色概念及均勻全染色猜想.近年來, 許多學者圍繞圖的各類均勻全染色做了大量研究[3-8].文獻[4]提出了鄰點可區(qū)別I-全染色的概念.文獻[5]給出了鄰點可區(qū)別I-均勻全染色的概念和鄰點可區(qū)別I-均勻全染色猜想.文獻[10]給出了若干Mycielski圖的鄰點可區(qū)別I-均勻全染色.本文根據(jù)路的第一類廣義Mycielski圖的構(gòu)造特征,運用函數(shù)構(gòu)造法研究并確立了這類圖鄰點可區(qū)別I-均勻全色數(shù).特別的,當t>3時，針對路的第一類廣義Mycielski圖Mn(Pt),根據(jù)n的取值分5種情況討論并給出了其鄰點可區(qū)別的I-均勻全色數(shù), 所得結(jié)果驗證了這類圖滿足鄰點可區(qū)別I-均勻全染色猜想：

1 基本概念和引理

定義1[4]對于階數(shù)不小于2的連通圖G(V,E),設(shè)f是從V(G)∪E(G)到{1,2,…,k}的映射,k為自然數(shù)，如果f滿足

(1)對?uv∈E(G),u≠v,有f(u)≠f(v);

(2)對?uv,uw∈E(G),v≠w,f(uv)≠f(uw);

(3)對?uv∈E(G),u≠v,C(u)≠C(v)，

則稱f為G的一個鄰點可區(qū)別的I-全染色(簡記為k-I-AVDTC).

定義2[5]設(shè)f是簡單連通圖G(V,E)

(|V(G)|≥2)的一個k-I-AVDTC，若滿足?i,j∈{1,2,…，k},i≠j,有

||Ti|-|Tj||≤1，

Ti=Vi∪Ei,

Vi={v|v∈V(G),f(v)=i},

Ei={e|e∈E(G),f(e)=i}.

定義3[11-12]對簡單圖G(V,E)，|V(G)|=p,n是自然數(shù)，Mn(G)稱為G的第一類廣義Mycielski圖，如果

V(Mn(G))=

{v01,v02,…,v0p;v11,v12,…,

v1p;…;vn1,vn2,…,vnp};

E(Mn(G))=

E(G)∪{vijvi+1,k|v0jv0k∈E(G),

1≤j,k≤p,i=0,1,…,n-1}.

2 主要結(jié)果與證明

定理1設(shè)P3為3階路圖，則

證明當t=3時，圖Mn(P3)中沒有相鄰的最大度點，且Δ(Mn(P3))=4.根據(jù)引理1，有

為證定理為真，只需給出圖Mn(P3)的一個4-I-AVDETC.為此構(gòu)造映射f:V(Mn(P3))∪E(Mn(P3))→{0,1,2,3}，令f為

f(v01v02)=0,f(v02v03)=1,

當n=0(mod 4)時，有

當n=1(mod 4)時，有

當n=2(mod 4)時，有

當n=3(mod 4)時，有

綜上，由定義2可知,f是圖Mn(P3)的一個4-I-AVDETC.

定理2設(shè)Pt為t(t>3)階路圖，則

證明當t>3時，圖Mn(Pt)中有相鄰的最大度點，且Δ(Mn(Pt))=4.根據(jù)引理1，有

Δ(Mn(Pt))+1=5.

情形1當n=0(mod 5)時，令f為

f(v01)=1,f(v02)=2,f(v03)=4,

f(v0j)=

f(v3j)=

f(vij)=

f(vijvi+1,j+1)=

f(vijvi-1,j+1)=

為驗證上述染色方法f是鄰點可區(qū)別的，下面給出各頂點的色集合:

由于頂點vi1(i=0,1,…,n)，vnj(j=1,2,…,t)，vit(i=0,1,…,n)的度均為2，頂點vn1，vnt的度均為1，而與這些點相鄰的頂點的度均為4，故這些點的色集合顯然與其相鄰頂點的色集合不同，因此無需再進一步驗證.綜上所述，此染色法f為鄰點可區(qū)別的,且各種顏色所染元素數(shù)為

從而由定義1可知，f是圖Mn(Pt)當n=0(mod 5)時的一個5-I-AVDETC.

情形2當n=1(mod 5)時，令f為

f(vij)=

f(vijvi+1,j+1)=

f(vijvi-1,j+1)=

邊v0jv1,j+1用3,3,4,4,0,0循環(huán)染色，邊v1jv0,j+1用4,0,0,3,3,4循環(huán)染色.

為驗證上述染色方法f是鄰點可區(qū)別的，下面給出各頂點的色集合:

同情形1，頂點vi1(i=0,1,…,n)，vnj(j=1,2,…,t)，vit(i=0,1,…,n)的色集合無需再進一步驗證.綜上所述，此染色f為鄰點可區(qū)別的,且各種顏色所染元素數(shù)均為

綜上，由定義1可知f是圖Mn(Pt)當n=1(mod 5)時的一個5-I-AVDETC.

情形3當n=2(mod 5)時，令f為頂點v01,v02,…,v0t依次用1,4,3,0,3循環(huán)染色；頂點v11,v12,…,v15用3,2,2,4,4染色;頂點v16,v17,…,v1t依次用2,2,2,4,4循環(huán)染色;頂點v21,v22,…,v2t依次用0,1,0,1,1,1循環(huán)染色；頂點v31,v32,…,v3t依次用4,4,4,2,2循環(huán)染色，且

f(vij)=

邊v0jv0,j+1(j=1,2,…,t-1)依次用4,2,4,2,3循環(huán)染色.

f(v1jv0,j+1)=0,j=1,2,…,t-1;

f(v1jv2,j+1)=3,j=1,2,…,t;

f(v2jv1,j+1)=4,j=1,2,…,t-1;

f(vijvi+1,j+1)=

f(vijvi-1,j+1)=

為驗證上述染色方法f是鄰點可區(qū)別的，下面給出各頂點的色集合:

同情形1，頂點vi1(i=0,1,…,n)，vnj(j=1,2,…,t)，vit(i=0,1,…,n)的色集合無需再進一步驗證.綜上所述，此染色f為鄰點可區(qū)別的,且有：

當t=0(mod 5)時，有

當t=1(mod 5)時，有

當t=2(mod 5)時，有

當t=3(mod 5)時，有

當t=4(mod 5)時，有

綜上，由定義1可知，f是圖Mn(Pt)當n=2(mod 5)時的一個5-I-AVDETC.

情形4當n=3(mod 5)時，令f為頂點v01,v02用0,4染色，頂點v03,v04,…,v0t依次用1,0,4,1,0循環(huán)染色；頂點v11用1染色;頂點v12,v13,…,v1t均用2染色;頂點v21,v22用3,0染色;頂點v23,v24,…,v2t依次用3,1,1,0,0循環(huán)染色；頂點v31，v32用1,2染色；頂點v33,v34,…,v3t依次用4,2,4,4,1循環(huán)染色,且

f(vij)=

邊v0jv0,j+1(j=1,2,…,t-1)依次用4,0,4,0,1循環(huán)染色.

f(vijvi+1,j+1)=

f(vijvi-1,j+1)=

f(vijvi+1,j+1)=

f(vijvi-1,j+1)=

為驗證上述染色方法f是鄰點可區(qū)別的，下面給出各頂點的色集合:

同情形1，頂點vi1(i=0,1,…,n)，vnj(j=1,2,…,t)，vit(i=0,1,…,n)的色集合無需再進一步驗證.綜上所述，此染色f為鄰點可區(qū)別的,且有：

當t=0(mod 5)時，有

當t=1(mod 5)時，有

當t=2(mod 5)時，有

當t=3(mod 5)時，有

當t=4(mod 5)時，有

綜上，由定義1可知，f是圖Mn(Pt)當n=3(mod 5)時的一個5-I-AVDETC.

情形5當n=4(mod 5)時，令f為頂點v01用0染色;頂點v02,v03,…,v0t依次用4,2,1,0,1循環(huán)染色；頂點v11用3染色;頂點v12,v13,…,v1t依次用3,3,4,2,3循環(huán)染色；頂點v21用2染色;頂點v22,v23,…,v2t依次用1,2,1,2,1循環(huán)染色；頂點v31用4染色;頂點v32,v33,…,v3t依次用0,0,0,4,4循環(huán)染色；頂點v41用1染色;頂點v42,v43,…,v4t依次用2,1,2,1,2循環(huán)染色；頂點v71,v72,…,v7t依次用3,2,3,3,3循環(huán)染色,且

f(vij)=

f(vijvi+1,j+1)=

f(vijvi-1,j+1)=

為驗證上述染色方法f是鄰點可區(qū)別的，下面給出各頂點的色集合：

同情形1，頂點vi1(i=0,1,…,n)，vnj(j=1,2,…,t)，vit(i=0,1,…,n)的色集合無需再進一步驗證.綜上所述，此染色f為鄰點可區(qū)別的,且有：

當t=0(mod 5)時，有

當t=1(mod 5)時，有

當t=2(mod 5)時，有

當t=3(mod 5)時，有

當t=4(mod 5)時，有

綜上，由定義1可知，f是圖Mn(Pt)當n=4(mod 5)時的一個5-I-AVDETC.

推論1設(shè)Pt為t(t≥3)階路，則

由引理1和引理2知此推論成立.

3 結(jié)語

本文研究了路的第一類廣義Mycielski圖Mn(Pt)的鄰點可區(qū)別I-均勻全色方法和鄰點可區(qū)別I-均勻全色數(shù),所得結(jié)果驗證了這類圖滿足鄰點可區(qū)別I-均勻全染色猜想.在后續(xù)的工作中,將進一步研究第二類廣義Mycielski圖mn(Pt)的鄰點可區(qū)別I-均勻全染色方法.