關(guān)于圖Pa,b的鄰點(diǎn)可區(qū)別染色

嚴(yán)謙泰

(安陽(yáng)師范學(xué)院 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，河南 安陽(yáng) 455000)

1 研究背景

圖的染色是圖論的重要研究?jī)?nèi)容，由計(jì)算機(jī)科學(xué)和信息科學(xué)等所產(chǎn)生的一般點(diǎn)可區(qū)別邊染色[1]、鄰點(diǎn)可區(qū)別邊染色[2-6]、鄰點(diǎn)可區(qū)別全染色[7]、鄰點(diǎn)強(qiáng)可區(qū)別全染色[8]等染色法，這些都是十分困難的問(wèn)題，至今文獻(xiàn)甚少。文中將通過(guò)具體的染色方法，給出圖Pa,b的鄰點(diǎn)可區(qū)別邊染色數(shù)、鄰點(diǎn)可區(qū)別全染色數(shù)、鄰點(diǎn)強(qiáng)可區(qū)別全染色數(shù)。

定義2[7]圖G(V,E)的一個(gè)正常全染色f:V∪E→{1,2,…,k}，如果滿足：

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

2)對(duì)任意的uv,vw∈E有f(uv)≠f(vw)，且C(u)≠C(v)。

則稱f是圖G(V,E)的一個(gè)鄰點(diǎn)可區(qū)別全染色，簡(jiǎn)記為k-AVETC。在k-AVDTC中最小的數(shù)k稱為圖G(V,E)的一個(gè)鄰點(diǎn)可區(qū)別全染色數(shù)，記為χat(G)=min{k|k-AVDTC}。

定義3[8]設(shè)G(V,E)是階數(shù)不小于3的簡(jiǎn)單連通圖，f是從V(G)∪E(G)到{1,2,…,k}的映射，滿足:

1) 對(duì)任意的邊uv∈E(G)，f(u)≠f(v)，f(u)≠f(uv)，f(v)≠f(uv);

2)對(duì)任意的兩相鄰邊uv，uw∈E(G)(v≠w)，f(uv)≠f(uw);

3)對(duì)任意的邊uv∈E(G)，其端點(diǎn)的色集合滿足C(u)≠C(v)，其中一頂點(diǎn)u的色集合

C(u)={f(u)}∪{f(v)|uv∈E(G)}

∪{f(uv)|uv∈E(G)}

則稱f是圖G的一個(gè)鄰點(diǎn)強(qiáng)可區(qū)別的全染色，簡(jiǎn)記作k-AVSDTC，且稱數(shù)

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

為G的鄰點(diǎn)強(qiáng)可區(qū)別的全染色數(shù)。

定義4[9]設(shè)u,v是兩個(gè)固定頂點(diǎn)，用b條內(nèi)部互不相交且長(zhǎng)度均為a的道路連接u,v的圖用Pa,b表示。

本文涉及的圖都是簡(jiǎn)單連通有限圖，未加說(shuō)明的術(shù)語(yǔ)與記號(hào)見文獻(xiàn)[10]。

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

引理2[7]如果簡(jiǎn)單圖G是階不小于3的圖，則χat(G)≥Δ(G)+1；如果簡(jiǎn)單圖G有兩個(gè)相鄰的最大度頂點(diǎn)，則χat(G)≥Δ(G)+2。

引理3[8]如果簡(jiǎn)單圖G是階不小于3的圖，則χast(G)≥Δ(G)+1;而G中至少有最大度頂點(diǎn)相鄰，則有χast(G)≥Δ(G)+2。

引理4[8]對(duì)于n階路Pn(n≥3)，有

χast(Pn)={4,n≡0(mod 2)

5,n≡1(mod 2)

……

即第1條路上的邊用1,2,…,b循環(huán)染色；第2條路上的邊用2,3,…,b，1循環(huán)染色；第3條路上的邊用3,4,…,b，1，2循環(huán)染色；……；第b條路上的邊用b，1,2,…,b-1循環(huán)染色。這是Pa,b的一個(gè)b-AVDEC。

定理2 對(duì)于圖Pa,b(a≥3,b≥3)，有χat(Pa,b)=b+1。

證明 情形1 對(duì)于圖Pa,3(a≥3)，有χat(Pa,3)=4。

由于Δ(Pa,3)=3，由引理2知，χat(Pa,b)≥4，下證χat(Pa,b)=4。Pa,3中每條路上一共有2a+1個(gè)頂點(diǎn)和邊。

故f是Pa,3的4-AVDTC。

故f是Pa,3的4-AVDTC。

綜上可知，χat(Pa,3)=4。

情形2 對(duì)于圖Pa,b(a≥3,b≥4)，由于Δ(Pa,b)=b，故χat(Pa,b)≥b+1，下證χat(Pa,b)=b+1。Pa,b(a≥3,b≥3)中每條路上一共有2a+1個(gè)頂點(diǎn)和邊。

第1條路上前2a個(gè)頂點(diǎn)和邊用1,2,…,b,b+1循環(huán)染色；

第2條路上的頂點(diǎn)和邊用1，3，4，…，b+1，2循環(huán)染色；

第3條路上的頂點(diǎn)和邊用1，4，5，…，b+1，2，3循環(huán)染色；

……

第b條路上的頂點(diǎn)和邊用1,b+1,2,3,…,b循環(huán)染色。

這是Pa,b的一個(gè)(b+1)-AVDTC。

……

這是Pa,b的一個(gè)(b+1)-AVDTC。

……

這是Pa,b的一個(gè)(b+1)-AVDTC。

一般地，當(dāng)2a+1≡i(mod(b+1))時(shí)，

……

……

綜上可知，f是Pa,b的一個(gè)(b+1)-AVDTC。

定理3 對(duì)于圖Pa,3(a≥4)，有

χast(Pa,3)={4,a≡0(mod 2)

5,a≡1(mod 2)

情形1.1 當(dāng)a≡0(mod 3)時(shí)，此時(shí)2a是3的倍數(shù)。

當(dāng)i≡1(mod 2)時(shí)：

當(dāng)i≡1(mod 2)時(shí)：

當(dāng)i≡1(mod 2)時(shí)：

這是Pa,3(a≥4)的一個(gè)4-AVSDTC。

情形1.2 當(dāng)a≡1(mod 3)時(shí)。

當(dāng)i≡1(mod 2)時(shí)：

當(dāng)i≡1(mod 2)時(shí)：

當(dāng)i≡1(mod 2)時(shí)：

這是Pa,3(a≥4)的一個(gè)4-AVSDTC。

情形1.3 當(dāng)a≡2(mod 3)時(shí)。

當(dāng)i≡1(mod 2)時(shí)：

當(dāng)i≡1(mod 2)時(shí)：

當(dāng)i≡1(mod 2)時(shí)：

這是Pa,3(a≥4)的一個(gè)4-AVSDTC。

情形2.1 當(dāng)a≡0(mod 5)時(shí)，

這是Pa,3(a≥4)的一個(gè)5-AVSDTC。

情形2.2 當(dāng)a≡1(mod 5)時(shí)，

這是Pa,3(a≥4)的一個(gè)5-AVSDTC。

情形2.3 當(dāng)a≡2(mod 5)時(shí)，

這是Pa,3(a≥4)的一個(gè)5-AVSDTC。

情形2.4 當(dāng)a≡3(mod 5)時(shí)，

這是Pa,3(a≥4)的一個(gè)5-AVSDTC。

情形2.5 當(dāng)a≡4(mod 5)時(shí)，

這是Pa,3(a≥4)的一個(gè)5-AVSDTC。

綜上可知，χast(Pa,3)={4,a≡0(mod 2)

5,a≡1(mod 2)。

定理4 對(duì)于圖Pa,b(a≥4,b≥4)，有χast(Pa,b)=b+1。

情形1 當(dāng)a≡0(mod 5)時(shí)。

第i條路上的頂點(diǎn)用1(i+1)(i+2)(i+3)(i+4)循環(huán)染色，i=1,2,…,b，其中i+1，i+2，i+3，i+4(≥b+2)是在模b(modb)的意義下。 第i條路上的邊用(i+2)(i+3)(i+4)1(i+1)循環(huán)染色。同定理3可驗(yàn)證f是Pa,b(a≥4,b≥4)的一個(gè)(b+1)-AVSDTC。

情形2 當(dāng)a≡1(mod 5)時(shí)。

情形3 當(dāng)a≡2(mod 5)時(shí)。

第i條路上的頂點(diǎn)用1(i+1)(i+2)(i+3)(i+4)循環(huán)染色，i=1,2,…,b，其中i+1，i+2，i+3，i+4(≥b+2)是在b(modb)模的意義下。 第i條路上的邊用(i+2)(i+3)(i+4)1(i+1)循環(huán)染色?？沈?yàn)證f是Pa,b(a≥4,b≥4)的一個(gè)(b+1)-AVSDTC。。

情形4 當(dāng)a≡3(mod 5)時(shí)。

情形5 當(dāng)a≡4(mod 5)時(shí)。

綜上可知，對(duì)圖Pa,b(a≥4,b≥4)，有χast(Pa,b)=b+1。