(廣義)Farey圖的彩虹連通性

劉素娟, 王林林

(1.天津科技大學(xué) 人工智能學(xué)院, 天津 300071; 2.中國礦業(yè)大學(xué) 數(shù)學(xué)學(xué)院, 江蘇 徐州 221116)

0 引言

彩虹連通數(shù)是一個自然的組合概念, 在信息的安全傳輸?shù)阮I(lǐng)域有重要的應(yīng)用[1-2].彩虹連通數(shù)的研究得到了眾多專家學(xué)者的關(guān)注[3-7].本文討論了Farey圖和廣義Farey圖的彩虹頂點連通數(shù), 彩虹連通數(shù)和完全彩虹連通數(shù)，其中所考慮的圖均為有限無向簡單圖, 未定義的術(shù)語和概念參見[8].

彩虹連通數(shù)的概念推廣包括強彩虹連通數(shù)[9], 彩虹k-連通數(shù)[10], 彩虹頂點連通數(shù)[11], 完全彩虹連通數(shù)[12]等.頂點著色圖中的所有內(nèi)部頂點都染不同顏色的路稱為彩虹路.頂點著色圖G是彩虹頂點連通的, 如果G中的任意兩個不同頂點之間都有一條彩虹路相連.定義圖G的彩虹頂點連通數(shù), 記為rvc(G).對于圖G=(V,E),c:V∪E→{1,2,…，k}是G的一個完全著色.圖G中的所有邊和內(nèi)部頂點都染不同顏色的路稱為完全彩虹路.若G中任意兩個不同頂點之間都有一條完全彩虹路相連, 則稱圖G是完全彩虹連通的,c為G的完全彩虹著色.定義圖G的完全彩虹連通數(shù)為其完全彩虹著色所需的最少的顏色數(shù), 記為trc(G).顯然,rvc(G)≥diam(G)-1,trc(G)≥2diam(G)-1.

MATULA[13]等人于1979年根據(jù)Farey序列提出了Farey圖的概念.

對于圖G中的頂點v,NG(v)表示v的鄰點構(gòu)成的集合.對于路P=v0v1…vk(k≥1),稱頂點v0,vk為路P的兩個端點; 記viPvj=vivi+1…vj(0≤i

定義1 Farey圖Fn(n≥0)是通過下面的迭代方法得到的.

1)F0是一條邊;

2) 當(dāng)n≥1時,Fn通過對Fn-1中第n-1步新增的每一條邊添加一個頂點, 并將這個頂點與這條邊的兩端點相連得到.

Farey圖F0,F1，F(xiàn)2，F(xiàn)3和F4.如圖1所示.記V(Fn)=V0∪V1∪…∪Vn,E(Fn)=E0∪E1∪…∪En其中V0=V(F0),E0=E(F0),Vi=V(Fi)V(Fi-1),Ei=E(Fi)E(Fi-1),即Vi和Ei分別為Fn在第i步新增的頂點集合和邊集合.ZHANG[14]等人研究了Farey圖的階數(shù), 邊數(shù), 度分布, 直徑, 平均距離等拓撲性質(zhì), 并證明了Farey圖是一個與某些復(fù)雜系統(tǒng)相關(guān)的網(wǎng)絡(luò)模型.接下來給出廣義Farey圖H(a,n)的概念.

圖1 Farey

定義2 對于正整數(shù)a和非負整數(shù)n, 定義廣義Farey圖H(a,n)如下:

1)H(a,0)=K3, 即H(a,0)是3個頂點的完全圖;

2) 當(dāng)n≥1時,H(a,n)通過對H(a,n-1)中在n-1步新增的每一條邊添加a個頂點, 并將這a個頂點與這條邊的兩端點相連.結(jié)果如下圖所示.

圖2給出了a=1,2,n=0,1,2時的廣義Farey圖.記V(H(a,n))=V0∪V1∪…∪Vn,E(H(a,n))=E0∪E1∪…∪En, 其中V0=V(H(a,0)),E0=E(H(a,0)),Vi=V(H(a,i))V(H(a,i-1)),Ei=E(H(a,i))E(H(a,i-1)), 即Vi和Ei分別是H(a,n)在第i步新增的頂點集合和邊集合.

圖2 廣義Farey圖H(a,n)

1 主要結(jié)論

首先給出Farey圖和廣義Farey圖的直徑.

命題1[14]對于Farey圖Fn,diam(Fn)=n(n≥1), 其中diam(Fn)是圖Fn的直徑.

命題2 對于廣義Farey圖H(a,n)(a≥1,n≥0),diam(H(a,n))=n+1, 其中diam(H(a,n))是圖H(a,n)的直徑.

證明當(dāng)a=1時,Fn+1是H(1,n)的一個頂點誘導(dǎo)子圖, 由Fn和H(1,n)的定義可得,diam(H(1,n))=diam(Fn+1)=n+1.當(dāng)a≥2時, 可以驗證diam(H(a,n))=diam(H(1,n))=n+1.

下面討論Farey圖和廣義Farey圖的彩虹頂點連通數(shù).首先給出嚴格彩虹頂點著色的定義.

定義3設(shè)c是圖G的一個頂點著色.若G中路P是彩虹路, 且兩端點的顏色與內(nèi)部頂點的顏色也不同, 則稱路P是嚴格彩虹路.若G中的任意兩個頂點之間都有一條嚴格彩虹路相連, 則稱c為圖C的嚴格彩虹頂點著色.

顯然, 嚴格彩虹頂點著色也是一個彩虹頂點著色.在嚴格彩虹路中, 兩端點的顏色可以相同.

定理1對于廣義Farey圖H(a,n)(a≥1,n≥0),n≤rvc(H(a,n))≤n+2.

證明由rvc(G)≥diam(G)-1和diam(H(a,n))=n+1可得rvc(H(a,n))≥n.為了證明rvc(H(a,n))≤n+2, 只需構(gòu)造H(a,n)的一個n+2種顏色的彩虹頂點著色.當(dāng)n=0,1時, 可以驗證rvc(H(a,n))=n成立.

下面通過歸納法證明:n≥2時, 存在H(a,n)的n+2種顏色的嚴格彩虹頂點著色cn.

定義H(a,1)的頂點著色c1如下: 首先將H(a,0)的3個頂點分別用顏色1,2,3染色; 然后將V1中的頂點用1,2,3中的與其兩個鄰點顏色不同顏色染色.可以驗證,c1是H(a,1)的3種顏色的相鄰頂點染不同顏色的嚴格彩虹頂點著色.假設(shè)ci-1是H(a,i-1)(2≤i≤n)的i+1種顏色的相鄰頂點染不同顏色的嚴格彩虹頂點著色.定義H(a,i)的i+2種顏色的頂點著色ci如下: 若v∈V(H(a,i-1)),ci(v)=ci-1(v);若v∈Vi,ci(v)=i+2, 其中i+2是新顏色.顯然,ci是H(a,i)的i+2種顏色的相鄰頂點染不同顏色的頂點著色.

接下來證明ci是嚴格彩虹頂點著色.

設(shè)u,v是H(a,i)中兩個頂點.

1) 當(dāng)u,v∈V(H(a,i-1))時, 由ci的定義可得, 在H(a,i-1)中存在一條u,v之間的嚴格彩虹路；

2) 當(dāng)u∈Vi,v∈V(H(a,i-1))時, 記u在H(a,i-1)中的兩個鄰點為u′,u″；

3) 當(dāng)v∈{u′,u″}時,u,v相鄰,顯然存在u,v之間的嚴格彩虹路；

4) 當(dāng)v?{u′,u″}時, 因為相鄰的頂點u′,u″染不同的顏色,u′或u″ (不妨設(shè)為u′)與v的顏色不同, 即ci(u′)≠ci(v).在H(a,i-1)中存在一條u′和v之間的所有頂點都染不同顏色的嚴格彩虹路P.從而, 路uu′Pv是u,v之間的嚴格彩虹路.當(dāng)u,v∈vi時, 設(shè)u,v在H(a,i-1)中的鄰點分別為u′,u″和v′,v″.當(dāng)v′∈{u′,u″}時,uv′v是u,v之間的嚴格彩虹路.當(dāng)v′?{u′,u″}時, 由前面的證明可知, 在H(a,i-1)中存在一條u′或u″(不妨設(shè)為u′) 到v′的所有頂點都染不同顏色的嚴格彩虹路P.從而, 路uu′Pv′v是u,v之間的嚴格彩虹路.因此,ci是H(a,i)的嚴格彩虹頂點著色.

綜上,cn是H(a,n)的n+2種顏色的彩虹頂點著色, 即rvc(H(a,n))≤n+2.

Farey圖Fn是廣義Farey圖H(1,n-1)的一個頂點誘導(dǎo)子圖, 在定理1中構(gòu)造了H(1,n-1)的彩虹頂點著色cn-1.定義Fn的頂點著色c.對于v∈V(Fn)?V(H(1,n-1)),cv=cn-1(v).由定理1的證明可知,c是Fn的n+1種顏色的彩虹頂點著色.結(jié)合命題 1,可得下面的推論.

推論1對于Farey圖Fn(n≥1), 有n-1≤rvc(Fn)≤n+1成立.

下面討論Farey圖和廣義Farey圖的彩虹連通數(shù).

首先考慮n=2k+1(k≥1)的情況.由rc(H(1,1))=2得到，存在H(1,1)的一個2種顏色的彩虹邊著色c0.假設(shè)H(1,1+2t)(0≤t

定義H(1,3+2t)的邊著色ct+1為: 若e∈E(H(1,1+2t)),ct+1(e)=ct(e);ct+1(ui1vi)=ct+1(ui2vi)=x1;ct+1(ui1wi1)=ct+1(ui2wi2)=x2;ct+1(wi1vi)=ct+1(wi2vi)=x3, 其中x1,x2,x3是新顏色.圖3(a)給出了新添加邊的著色方法.顯然, 邊著色ct+1使用了2+3(t+1)種顏色.

接下來證明ct+1是H(1,3+2t)的一個彩虹邊著色.

任取H(1,3+2t)中的兩個頂點u,v.當(dāng)u,v∈V(H(1,1+2t))時,在H(1,1+2t)中存在一條u,v之間的彩虹路.

1) 當(dāng)u∈V(H(1,1+2t)),v∈V2+2t∪V3+2t(不妨設(shè)v∈{vi,wi1,wi2})時, 則vui1P1u或vui2P2u(其中P1和P2分別是H(1,1+2t)中的從u到ui1和ui2的彩虹路) 是u,v之間的一條彩虹路；

2) 當(dāng)u,v∈V2+2t∪V3+2t且u,v∈{vi,wi1,wi2}時, 則在頂點集合{ui1,ui2,vi,wi1,wi2}誘導(dǎo)的子圖中存在u,v之間的一條彩虹路.

3) 考慮u,v∈V2+2t∪V3+2t且u∈{vi,wi1,wi2},v∈{vj,wj1,wj2}(i≠j)的情況.令P1,P2分別表示H(1,1+2t)中的ui1到uj1和ui2到uj2的彩虹路； 由ct+1的定義可得, 當(dāng)u=wi1時,wi1ui1P1uj1vj,wi1ui1P1uj1wj1和wi1ui1P1uj1vjwj2都是彩虹路,即u,v之間存在一條彩虹路.當(dāng)u=wi2或u=vi時, 可類似證明u,v之間存在一條彩虹路.

圖3 (a) H(1,3+2t)的新增邊著色； (b) H(1,2)的彩虹邊著色

下面討論Farey圖和廣義Farey圖的完全彩虹連通數(shù).首先給出嚴格完全彩虹著色的概念.

定義4設(shè)c是圖G的一個完全著色.若G中的路P是完全彩虹路, 且兩端點的顏色與內(nèi)部頂點和邊的顏色都不同, 則稱路P是一條嚴格完全彩虹路.若G中的任意兩個頂點之間都有一條嚴格完全彩虹路相連, 則稱完全著色c為G的嚴格完全彩虹著色.

顯然, 嚴格完全彩虹著色也是一個完全彩虹著色.在嚴格完全彩虹路中, 兩端點的顏色可能相同.

首先考慮n=2k(k≥1)的情況.構(gòu)造H(1,2i)(0≤i≤k)的一個5i+3種顏色的完全著色ci.令H(1,0)=v1v2v3v1, 即H(1,0)是一個3長圈.定義H(1,0)的3種顏色的完全著色c0為:c0(v1)=c0(v2v3)=1,c0(v2)=c0(v1v3)=2,c0(v3)=c0(v1v2)=3.可以驗證,c0是H(1,0)的3種顏色的相鄰頂點染不同顏色的嚴格完全彩虹著色.假設(shè)ct是H(1,2t)(0≤t

在H(1,2t+2)中,記E2t={ei=ui1ui2|1≤i≤3·22t} ,V2t+1={vi|1≤i≤3·22t},V2t+2={wi1,wi2|1≤i≤3·22t}, 在第2t+1和2t+2步新增的2長路分別為Pi=ui1viui2,Pij=uijwijvi,1≤i≤3·22t,j=1,2.

定義H(1,2t+2)的完全著色ct+1:

1) 若e∈E(H(1,2t)),ct+1(e)=ct(e);

2) 若v∈V(H(1,2t)),ct+1(v)=ct(v);

3) 若e∈E2t+1,ct+1(e)=x1;

4) 若v∈V2t+1,ct+1(v)=x2;

路Pij=uijwijvi(1≤i≤3·22t,j=1,2)的內(nèi)部頂點和邊依次用x3,x4,x5染色, 其中xi(1≤i≤5)是新顏色.新增的邊和頂點的染色方法如圖4(a)所示.顯然,ct+1是H(1,2t+2)的5(t+1)+3種顏色的相鄰頂點染不同顏色的完全著色.

接下來證明ct+1是嚴格完全彩虹著色.

設(shè)u,v是H(1,2t+2)中兩個頂點.

圖4 (a) H(1,2t+2)新增邊的頂點著色； (b) H(1,1)的完全著色； (c) H(2,1)的完全著色

關(guān)于Farey圖和廣義Farey圖的完全彩虹連通數(shù), 有下面的結(jié)論.

定理3對于Farey圖Fn和廣義Farey圖H(a,n), 有下面的結(jié)論成立:

下面討論a≥2時的H(a,n)的完全彩虹連通數(shù).由diam(H(a,n))=n+1可得,rc(H(a,n))≥2n+1.

考慮n=2k+1(k≥0)的情況.設(shè)V(H(a,0))={v1,v2,v3}.定義H(a,1)的6種顏色的嚴格完全彩虹著色c1如下：

c1(v1)=c1(v2v3),c1(v2)=c1(v1v3)=x2,c1(v3)=c1(v1v2)=x3;

對于H(a,1)在第1步新增的2長的路P=vivvj(其中vi,vj∈V(H(a,0))),c1(viv)=4,c1(v)=5,c1(vvj)=6,其中4, 5, 6是新顏色.H(2,1)的完全著色c1如圖4(c)所示.可以驗證c1是H(a,1)的6種顏色的嚴格完全彩虹著色, 且滿足條件: 長度為1的路的邊和頂點都染不同的顏色.假設(shè)ct是H(a,2t+1)的一個5t+6種顏色的嚴格完全彩虹著色, 且滿足條件: 長度為1的路的邊和頂點都染不同的顏色.

定義H(a,2t+3)的完全著色ct+1如下:

若e∈E(H(a,2t+1)),ct+1(e)=ct(e);

若v∈V(H(a,2t+1)),ct+1(v)=ct(v);

若e∈E2t+2,ct+1(e)=x1;

若v∈V2t+2,ct+1(v)=x2;

對于H(a,2t+3)在第2t+3步新增的2長的路P=vivvj(其中vi∈V(H(a,2t+1)),vj∈V2t+2),ct+1(viv)=x3,ct+1(v)=x4,ct+1(vvj)=x5, 其中xi(1≤i≤5)是新顏色.顯然,ct+1是H(1,2t+3)的5(t+1)+6種顏色的完全著色, 且滿足條件: 長度為1的路的邊和頂點都染不同的顏色.

當(dāng)1≤n≤3時, 可以驗證rvc(Fn)=diam(Fn)-1,trc(Fn)=diam(Fn),rc(Fn)=2diam(Fn)-1.下面給出一個猜想.

猜想1對于Farey圖Fn(n≥1), 有rvc(Fn)=diam(Fn)-1;trc(Fn)=diam(Fn);rc(Fn)=2diam(Fn)-1成立.