三類K重Mycielski圖的鄰點強可區(qū)別E-全染色

李雨虹,強會英,王洪申

(1.蘭州交通大學(xué) 數(shù)理學(xué)院，甘肅 蘭州 730070，2.蘭州理工大學(xué) 機電工程學(xué)院，甘肅 蘭州 730050)

1 引言

圖染色理論是圖論[1]里面很重要并且應(yīng)用很廣泛的一門學(xué)科，它來源于1852年“四色猜想”問題的提出. 1993年，A.C.Burris和R.H.Schelp首次提出了圖的點可區(qū)別正常邊染色的概念；2002年，張忠輔，劉林忠等教授在點可區(qū)別正常邊染色的基礎(chǔ)上提出了圖的鄰強邊染色[2]；2005年，張忠輔，陳祥恩等教授結(jié)合學(xué)習(xí)傳播過程中的干擾和共振現(xiàn)象提出了圖的鄰點可區(qū)別全染色[3]；2007年，張忠輔，程輝等人提出了圖的鄰點強可區(qū)別全染色[4]，文獻(xiàn)[5]是鄰點強可區(qū)別E-全染色的一些結(jié)果.本文在文獻(xiàn)[5]的基礎(chǔ)上得到了路圖，圈圖和星圖的廣義Mycielski圖的鄰點強可區(qū)別區(qū)別E-全染色，下面給出相關(guān)的定義：

2 基本概念

定義1[4,5]設(shè)圖G是階數(shù)至少為2的連通圖， 映射f:V(G)∪E(G)→{1,2,…,k},其中k為正整數(shù)，C(u)={f(u)}∪{f(v)}∪{f(uv)|uv∈E(G),v∈V(G)}如果f滿足：

(1)對任意的uv∈E(G),f(u)≠f(v),f(u)≠f(uv),f(v)≠f(uv);

(2)對任意的uv,uw∈E(G),u≠v,f(uv)≠f(uw);

(3)對任意的uv∈E(G),u≠v,C(u)≠C(v).

則稱f為圖G的k-鄰點強可區(qū)別全染色，簡記為k-AVSDTC.又稱

χast(G)=min{k|G有k-AVSDTC}

為G的鄰點強可區(qū)別全色數(shù).

定義2[5]設(shè)圖G是階數(shù)至少為2的連通圖，映射f:V(G)∪E(G)→{1,2,…,k}，其中k為自然數(shù)，C(u)={f(u)}∪{f(v)}∪{f(uv)|uv∈E(G),v∈V(G)}.如果f滿足：

(1)對任意的uv∈E(G),u≠v,f(u)≠f(v),f(u)≠f(uv);

(2)對任意的uv∈E(G),u≠v,C(u)≠C(v).

則稱f為G的k-鄰點強可區(qū)別E-全染色，簡記為k-E-AVSDETC,又稱

為圖的鄰點強可區(qū)別E-全色數(shù).

由圖的鄰點強可區(qū)別全染 色和圖的鄰點強可區(qū)別E-全染色的概念，下面引理成立：

定義3[6]對圖G(V,E),μ(G)稱為G的Mycielski,V(μ(G))=V(G)∪V′∪{w},E(μ(G))=E(G)∪{uv′|u∈V(G),v′∈V′,且uv∈E(G)}∪{wv′|v′∈V′},其中w?V(G),V′={v′|v∈V(G)}

定義4[7]設(shè)G的頂點集合為V(G)={u1i|i=1,2,…,n}的簡單圖，n是正整數(shù)，稱Mk(G)為G的k重Mycielski圖，其中k≥2,如果

V(Mk(G))={u1.1,u1.2,…,u1.n；u2.1,u2.2,…,u2.n；…；uk.1,…,uk.n}∪{w}

E(Mk(G))=E(M(G))∪{uijui+1,l|u1ju1l∈E(G),1≤j,l≤n,1≤i≤k-1,}∪{wvkj|vkj∈V(G),1≤j≤n}.

3 主要結(jié)論及其證明

定理1 設(shè)Pn是n(n≥3)階的路，則有

2,j≡0(mod2),1≤i≤k;1≤j≤n.φ(w)=3,由圖的結(jié)構(gòu)知，|C(w)|≥3 ，下面分兩種情形考慮：

情形1：當(dāng)|C(w)|=3 時，則點uij(除了u1j)和點w在鄰點強可區(qū)別E-全染色的條件下，必存在j∈{1,2,…,n}，使得C(u1j)=C(u1,j+1),與定義矛盾.

f(uij)={1,j≡1(mod2),

2,j≡0(mod2)1≤i≤k;1≤j≤n.f(w)=5.f(u1j,u1,j+1)=3,1≤j≤n-1.

邊uijui+1,l的染法分以下四種情況：

當(dāng)i≡0(mod4)時：

f(uijui+1,j-1)=3,1≤i≤k-1;2≤j≤n.

f(uijui+1,j+1)=3,1≤i≤k-1;1≤j≤n-1.

當(dāng)i≡1(mod4)時：

f(uijui+1,j-1)={3,j≡1(mod2),

4,j≡0(mod2),

1≤i≤k-1;2≤j≤n.

f(uijui+1,j+1)={3,j≡1(mod2),

4,j≡0(mod2),

1≤i≤k-1;1≤j≤n-1.

當(dāng)i≡2(mod4)時：

f(uijui+1,j-1)=4,1≤i≤k-1;2≤j≤n.

f(uijui+1,j+1)=4,1≤i≤k-1;1≤j≤n-1.

當(dāng)i≡3(mod4)時：

f(uijui+1,j-1)={3,j≡0(mod2),

4,j≡1(mod2),

1≤i≤k-1;2≤j≤n.

f(uijui+1,j+1)={3,j≡0(mod2),

1,j≡1(mod2),

1≤i≤k-1;1≤j≤n-1.

f(wvkj)={1,j≡0(mod2),

2,j≡1(mod2),1≤j≤n.

此時，各點的色集合的補集為：

當(dāng)i≡0(mod4)或i≡1(mod4)時：

{5},j≡0(mod2),

1≤i≤k-1;1≤j≤n.

當(dāng)i≡2(mod4)或i≡3(mod4)時：

{5},j≡0(mod2),

1≤i≤k-1;1≤j≤n.

當(dāng)k≡0(mod4)時：

{4},j≡1(mod2),

1≤j≤n.

當(dāng)k≡1(mod4)時：

當(dāng)k≡2(mod4)時：

{4},j≡0(mod2),1≤j≤n.

當(dāng)k≡3(mod4)時：

顯然，對?uv∈E(G),有C(u)≠C(v),故結(jié)論成立.

定理2 設(shè)Sn是n(n≥4)階的星圖，則有

f(uij)={1,j=1,

2,2≤j≤n,1≤i≤k.f(w)=5.f(u11u1j)=3,2≤j≤n.

邊uijui+1,l的染法如下：

f(uijui+1,1)={3,i≡0(mod4)或i≡3(mod4),

4,i≡1(mod4)或i≡2(mod4),

1≤i≤k-1;2≤j≤n.

f(ui1ui+1,j)={3,i≡0(mod4)或i≡1(mod4),

4,i≡2(mod4)或i≡3(mod4),

1≤i≤k-1;2≤j≤n.

f(wvkj)={2,j=1,

1,2≤j≤n.

此時，各點的色集合的補集為：

當(dāng)i≡0(mod4)或i≡1(mod4)時：

{5},2≤j≤n,1≤i≤k-1.

當(dāng)i≡2(mod4)或i≡3(mod4)時：

{5},2≤j≤n,1≤i≤k-1.

點ukj的色集合的補集分以下四種情況：

當(dāng)k≡0(mod4)時：

{3},2≤j≤n.

當(dāng)k≡1(mod4)時：

當(dāng)k≡2(mod4)時：

{4},2≤j≤n.

當(dāng)k≡3(mod4)時：

顯然， 對?uv∈E(G),有C(u)≠C(v)，故結(jié)論成立.

定理3 設(shè)Cn是n(n≥4)階的圈圖，則有

6,n≡1(mod2),(k≥3).

證明下面分兩種情況討論：

f(uij)={1,j≡1(mod2),

2,j≡0(mod2),1≤i≤k;1≤j≤n.f(w)=5.

f(u1ju1,j+1)=3,1≤j≤n-1.f(u11u1n)=3.

邊uijui+1,l的染法分以下四種情況：

當(dāng)i≡0(mod4)時：

f(uijui+1,j-1)=3,1≤i≤k-1;2≤j≤n.

f(uijui+1,j+1)=3,1≤i≤k-1;1≤j≤n-1.

當(dāng)i≡1(mod4)時：

f(uijui+1,j-1)={3,j≡1(mod2),

4,j≡0(mod2),

1≤i≤k-1;2≤j≤n.

f(uijui+1,j+1)={〗3,j≡1(mod2),

4,j≡0(mod2),

1≤i≤k-1;1≤j≤n-1.

當(dāng)i≡2(mod4)時：

f(uijui+1,j-1)=4,1≤i≤k-1;2≤j≤n.

f(uijui+1,j+1)=4,1≤i≤k-1;1≤j≤n-1.

當(dāng)i≡3(mod4)時：

f(uijui+1,j-1)={3,j≡0(mod2),

4,j≡1(mod2),

1≤i≤k-1;2≤j≤n.

f(uijui+1,j+1)={3,j≡0(mod2),

4,j≡1(mod2),

1≤i≤k-1;1≤j≤n-1.

f(uinui+1,1)={3,i≡0(mod4)或i≡3(mod4),

4,i≡1(mod4)或i≡2(mod4),

1≤i≤k-1.

f(ui1ui+1,n)={3,i≡0(mod4)或i≡1(mod4),

4,i≡2(mod4)或i≡3(mod4),

1≤i≤k-1.

f(wvkj)={1,j≡0(mod2),

2,j≡1(mod2),1≤j≤n.

此時，各點的色集合的補集為：

當(dāng)i≡0(mod4)或i≡1(mod4)時：

{5},j≡0(mod2),1≤i≤k-1;1≤j≤n.

當(dāng)i≡2(mod4)或i≡3(mod4)時：

{5},j≡0(mod2),1≤i≤k-1;1≤j≤n.

點ukj的色集合的補集分以下四種情況：

當(dāng)k≡0(mod4)時：

{4},j≡1(mod2),1≤j≤n.

當(dāng)k≡1(mod4)時：

當(dāng)k≡2(mod4)時：

{4},j≡0(mod2),1≤j≤n.

當(dāng)k≡3(mod4)時：

顯然， 對?uv∈E(G),有C(u)≠C(v),故結(jié)論成立.

2,j≡0(mod2),1≤i≤k;1≤j≤n-1.由圖的結(jié)構(gòu)知，|C(w)|≥4，下面分兩種情形考慮：

情形2.1：當(dāng)|C(w)|=4時，則點uij(除了u1j)和點w在鄰點強可區(qū)別E-全染色的條件下，必存在j∈{1,2,…,n}，使得C(u1j)=C(u1,j+1)與定義矛盾.

f(uij)={1,j≡1(mod2),

2,j≡0(mod2)1≤i≤k;1≤j≤n-1.f(uin)=3,1≤i≤k.f(w)=4.

f(u1ju1,j+1)={3,1≤j≤n-2,

5,j=n-1,f(u11u2n)=f(u1nu21)=f(u11u1n)=2.

f(u1ju2,j-1)={3,j≡0(mod2),

4,j≡1(mod2),2≤j≤n.

f(u1ju2,j-+)={3,j≡0(mod2),

4,j≡1(mod2),1≤j≤n-2.f(u1,n-1u2,n)=1.

邊uijui+1,l的染法如下：

f(uijui+1,j-1)

={6,i≡1(mod4)或i≡2(mod4),

5,i≡0(mod4)或i≡3(mod4),

2≤i≤k-1;2≤j≤n.

f(uijui+1,j+1)

={6,i≡1(mod4)或i≡2(mod4),

5,i≡0(mod4)或i≡3(mod4),

2≤i≤k-1;2≤j≤n-1.

f(ui1ui+1,n)=f(uinui+1,1)

={6,i≡1(mod4)或i≡2(mod4),

5,i≡0(mod4)或i≡3(mod4),

2≤i≤k-1.

當(dāng)k≡0(mod4)或k≡2(mod4)時：

f(wvkj)={2,j≡1(mod2),

1,j≡0(mod4),

1≤j≤n.

當(dāng)k≡1(mod4)時：

f(wvkj)=6,1≤j≤n.

當(dāng)k≡3(mod4)時：

f(wvkj)=5,1≤j≤n.

此時，各點的色集合的補集為：

{4,5,6},j≡0(mod2),

1≤j≤n-2.

{4,5},j≡1(mod2),

1≤j≤n-2.

當(dāng)i≡0(mod4)時：

{3,4,6},2≤j≤n-2,

3≤i≤k-1.

當(dāng)i≡1(mod4)時：

{3,4},2≤j≤n-2,

3≤i≤k-1.

當(dāng)i≡2(mod4)時：

{3,4,5},2≤j≤n-2,

3≤i≤k-1.

當(dāng)i≡3(mod4)時：

{3,4},2≤j≤n-2,

3≤i≤k-1.

當(dāng)k≡0(mod4)時：

{3,6},3≤j≤n-2.

當(dāng)k≡1(mod4)時：

{φ},3≤j≤n-2.

當(dāng)k≡2(mod4)時：

{3,5},3≤j≤n-2.

當(dāng)k≡3(mod4)時：

{φ},3≤j≤n-2.

顯然， 對?uv∈E(G),有C(u)≠C(v),故結(jié)論成立.

[參考文獻(xiàn)]

[1]Bondy J A. Graph theory with applications [J]. Journal of the Operational Research Society, 1977, 28(1):237-238.

[2]Zhang Z,Liu L,Wang J.Adjacent strong edge coloring of graphs [J].Applied Mathematics Letters,2002,15(5):623-626.

[3]張忠輔,陳祥恩,李敬文,等.關(guān)于圖的鄰點可區(qū)別全染色[J].中國科學(xué),2004,34(5):574-583.

[4]張忠輔,程輝,姚兵,等.圖的鄰點強可區(qū)別的全染色[J].中國科學(xué),2007,37(9):1073-1082.

[5]顧忠棟.若干圖的鄰點強可區(qū)別E-全染色[D].蘭州:蘭州交通大學(xué),2017.

[6]張忠輔,李敬文,田雙亮,等.圈的Mycielski圖的均勻全染色[J].蘭州交通大學(xué)學(xué)報,2003, 22(6):1-3.

[7]強會英,晁福剛,張忠輔.完全圖的廣義Mycielski圖的鄰點可區(qū)別的全色數(shù)[J].蘭州大學(xué)學(xué)報:自然科學(xué)版,2006,42(2):99-101.