蛛網(wǎng)圖的鄰和可區(qū)別染色

劉 歡, 強(qiáng)會(huì)英, 譚鈞銘

(蘭州交通大學(xué) 數(shù)理學(xué)院, 甘肅 蘭州 730070)

0 引言

圖的染色問(wèn)題是圖論中最古老的問(wèn)題之一,在現(xiàn)實(shí)生活中有著廣泛應(yīng)用.2013年,Flandrin等人首次提出圖的鄰和可區(qū)別染色的概念,并給出了一些特殊圖的鄰和可區(qū)別邊色數(shù)[1].隨后,Pilsniak等人給出了鄰和可區(qū)別全染色的定義[2],得到了完全圖、圈、二部圖等圖的鄰和可區(qū)別全色數(shù).蛛網(wǎng)圖是一個(gè)重要的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu),對(duì)于網(wǎng)絡(luò)權(quán)的分配和通信網(wǎng)絡(luò)的設(shè)計(jì)有重要的指導(dǎo)作用[3].2014年,張東翰研究了蛛網(wǎng)圖的鄰強(qiáng)邊染色,得到了其鄰強(qiáng)邊色數(shù)[4].2018年,李永艷討論了蛛網(wǎng)圖的鄰點(diǎn)可區(qū)別V-全染色,得到其鄰點(diǎn)可區(qū)別V-全色數(shù)[5].

受上述研究啟發(fā),本文討論了蛛網(wǎng)圖的鄰和可區(qū)別邊染色與全染色問(wèn)題,得到了蛛網(wǎng)圖的鄰和可區(qū)別邊色數(shù)和全色數(shù).文中涉及的圖均是有限、無(wú)向的簡(jiǎn)單圖,記號(hào)V(G)、E(G)、Δ(G)、GΔ分別表示圖G的頂點(diǎn)集、邊集、最大度和全體最大度頂點(diǎn)在圖G中的導(dǎo)出子圖.符號(hào){x1,x2,…,xn}→{a1,a2,…,an}表示用顏色序列a1,a2,…,an去染元素序列x1,x2,…,xn,其他未加說(shuō)明的術(shù)語(yǔ)C5、[k]、C(x)、S(u),見(jiàn)相關(guān)文獻(xiàn)[6-8].

1 預(yù)備知識(shí)

猜想1[2]若圖G是階至少為3的簡(jiǎn)單連通圖,且G≠C5,則ndi∑(G)≤Δ(G)+2.

定義4[3]蛛形圖Sk的頭點(diǎn)為v0,從v0出發(fā)有k(k≥3)條路,除v0外,每條路有k個(gè)點(diǎn),共有n(n=k2+1)個(gè)點(diǎn),刪去v0后,這k條路分別記為pi=vi1vi2…vik(1≤i≤k),eij表示pi中連接vi(j-1)和vij(1≤i≤k,2≤j≤k)的邊,連接v0和vi1的邊記為ei1(1≤i≤k).

定義5[4]設(shè)有蛛形圖Sk,在Sk中添加邊v1jv2j,v2jv3j,v3jv4j,v4jv5j,…,v(k-1)jvkj,vkjv1j(1≤j≤k-1)而得到的圖稱為蛛網(wǎng)圖,記為wk.

引理1[8]對(duì)于簡(jiǎn)單圖G,ndi∑(G)≥χ'a(G)≥Δ(G).若圖G有相鄰最大度點(diǎn),則ndi∑(G)≥Δ(G)+1.

2 主要結(jié)論

證明1) 當(dāng)k=3時(shí),因?yàn)镚Δ≠?,根據(jù)引理1知,ndi∑(G)≥Δ(G)+1=5.下面，給出圖W3的一個(gè)5-鄰和可區(qū)別邊染色

{v0v11,v0v21,v0v31}→{1,3,5};{v11v21,v21v31,v31v11}→{4,2,3};

{v11v12,v21v22,v31v32}→{2,5,1};{v12v22,v22v32,v32v12}→{3,4,5};

{v12v13,v22v23,v32v33}→{4,1,2}.

按上述染法各點(diǎn)色集合與色數(shù)和,如表1所示.

表1 圖W3各點(diǎn)色集合C(vij)和色數(shù)和s(vij)的情況

C(v11)表示與v11點(diǎn)相連的各邊色集合,s(v11)表示v11點(diǎn)的色數(shù)和.(下表同)

從表1易見(jiàn)f是圖W3的5-鄰和可區(qū)別邊染色.

2) 當(dāng)k=4時(shí),因?yàn)镚Δ≠?,根據(jù)引理1知,ndi∑(G)≥Δ(G)+1=5.下面，給出圖W4的一個(gè)5-鄰和可區(qū)別邊染色f:

f(v0vi1)=i,(1≤i≤4);f(vi1vi+1,1)=(i+2)(mod 4),(1≤i≤4);f(vi1vi2)=5,(1≤i≤4);

其余邊按如下序列染法

{v12v22,v22v32,v32v42,v42v12}→{4,3,2,3};

{v12v13,v22v23,v23v33,v42v43}→{2,1,4,1};

{v13v23,v23v33,v33v43,v43v13}→{3,2,5,4};

{v13v14,v23v24,v33v34,v43v44}→{1,5,1,3}.

按上述染法有C(v0)={1,2,3,4},s(v0)=10.其余各點(diǎn)情況，如表2所示.

表2 圖W4各點(diǎn)色集合C(vij)和色數(shù)和s(vij)的情況

由表2易得f是圖W4的5-鄰和可區(qū)別邊染色.

3) 當(dāng)k≥5時(shí),因?yàn)镚Δ=?,根據(jù)引理1知,ndi∑(G)≥Δ(G)=k.下面給出圖Wk的一個(gè)k-鄰和可區(qū)別邊染色f,分成以下兩種情況討論:

情況1 當(dāng)k≡1(mod 2)時(shí),

①i≡1(mod 2),令f(v0vi1)=i,(1≤i≤k)，

②i≡0(mod 2),令f(v0vi1)=i,(1≤i≤k)，

當(dāng)k≡1(mod 2)時(shí),C(v0)={1,2,3,4,…,k};C(vik)={i-2};

C(vij)={(i+2(j-1))(modk),(i+2(j-1)+4)(modk),

(i+2(j-1)+2)(modk),(i+2(j-1)+3)(modk)},1≤i≤k, 1≤j≤k-1.

得到

情況2 當(dāng)k≡0(mod 2)時(shí),

①i≡1(mod 2),

②i≡0(mod 2),

f(vijv(i+1)j)=f(vi(j+1)vi(j+2)),(1≤i≤k-1,1≤j≤k-2);

f(vkjv1j)=f(vk(j+1)vk(j+2)),(1≤j≤k-2);

f(vi(k-1)v(i+1)(k-1))=f(v0vi1),(1≤i≤k-1);f(vk(k-1)v1(k-1))=f(v0vk1).

當(dāng)k≡0(mod 2)時(shí),

C(v0)={1,2,3,4,…,k};

C(vij)={(i+2(j-1)+1)(modk),(i+2(j-1)+5)(modk),(i+2(j-1)+3)(modk),

得到

s(vik)=i-1,(1≤i≤k).

綜上所述,此定理成立.經(jīng)驗(yàn)證,蛛網(wǎng)圖的鄰和可區(qū)別邊染色符合猜想1.

f(vijvi(j+1))=(i+j+2)(mod 6),(1≤i≤3, 0≤j≤3 )；

{v11v21,v21v31,v31v11}→{6,2,1}；

{v12v22,v22v32,v32v12}→{1,3,2}；

f(v0)=1；f(vij)=i+j,(1≤i≤3, 1≤j≤3 ).

按上述染法各點(diǎn)色集合與色數(shù)和，如表3所示.

表3 圖W3各點(diǎn)色集合C(vij)和色數(shù)和c(vij)的情況

f(vijvi(j+1))=(i+j+2)(mod 6),(1≤i≤4,0≤j≤4);

f(vijv(i+1)j)=i+j-1,(1≤i≤3,1≤j≤3);

f(vkjv1j)=1+j,(1≤j≤3).f(v0)=1;

f(vij)=(i+j)(mod 6),(2≤i≤4, 1≤j≤4 );

{v11,v12,v13,v14}→{6,1,2,5}.

此時(shí),C(v0)={1,3,4,5,6},c(v0)=21.其余各點(diǎn)情況如下表所示.

由表4可,f是圖W4的6-鄰和可區(qū)別全染色.

表4 圖W4各點(diǎn)色集合C(vij)和色數(shù)和c(vij)的情況

f(v0)=6;f(vij)=(i+2j-1)(mod 6),(1≤i≤4,1≤j≤5);{v24,v45}→{6,4};

{v51,v52,v53,v54,v55}→{3,2,4,6,1}.f(v0vi1)=i,(1≤i≤5);

其余邊按如下序列染法，

{v11v21,v21v31,v31v41,v41v51,v51v11}→{5,6,1,2,4};

{v12v22,v22v32,v32v42,v42v52,v52v12}→{1,2,3,4,3};

{v11v12,v21v22,v31v32,v41v42,v51v52}→{6,4,5,6,1};

{v13v23,v23v33,v33v43,v43v53,v53v13}→{3,4,6,1,2};

{v12v13,v22v23,v32v33,v42v43,v52v53}→{5,6,1,5,6};

{v13v14,v23v24,v33v34,v43v44,v53v54}→{1,5,3,2,5};

{v14v15,v24v25,v34v35,v44v45,v54v55}→{5,1,5,1,2};

{v14v24,v24v34,v34v44,v44v54,v54v14}→{4,2,6,4,3}.

按上述染法有C(v0)={1,2,3,4,5,6},c(v0)=21.其余各點(diǎn)情況，如表5和表6所示.

表5 圖W5各點(diǎn)C(vij)的情況

表6 圖W5各點(diǎn)c(vij)的情況

由表6易見(jiàn)，f是圖W5的6-鄰和可區(qū)別全染色.

對(duì)于圖G中的鄰和可區(qū)別邊染色,規(guī)律同定理1.對(duì)于圖G的點(diǎn)染色

f(v0)=k+1;f(vij)=(f(vi(j-1)vij)+1)(modk),(1≤i≤k, 1≤j≤k).

按上述染法得色集合及色數(shù)和，如下所示.

① 當(dāng)k≡0(mod 2)時(shí),C(v0)={1,2,3,…,k,k+1};

C(vij)={(i+2(j-1)+1)(modk),(i+2(j-1)+5)(modk),(i+2(j-1)+3)(modk),

C(vik)={i-1,i},(1≤i≤k).

得到

② 當(dāng)k≡1(mod 2)時(shí),C(v0)={1,2,3,…,k,k+1};C(vij)={(i+2(j-1))(modk),

(i+2(j-1)+4)(modk),(i+2(j-1)+2)(modk),(i+2(j-1)+3)(modk),

(i+2(j-1)+1)(modk)},(1≤i≤k,1≤j≤k-1);C(vik)={i-2,i-1}.

得到

綜上所述,f是圖Wk的一個(gè)k+1-鄰和可區(qū)別全染色.經(jīng)驗(yàn)證,蛛網(wǎng)圖的鄰和可區(qū)別全染色符合猜想2.由此可見(jiàn),蛛網(wǎng)圖的鄰和可區(qū)別染色滿足圖的鄰和可區(qū)別邊染色和全染色猜想.