朱虹州，孟吉翔

(新疆大學(xué) 數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院，新疆 烏魯木齊 830046)

0 概念

令G=(V(G),E(G))是一個(gè)簡(jiǎn)單圖,F是G中的邊集,如果G ?F不連通且至少有兩個(gè)分支包含圈,那么稱F是G的一個(gè)圈邊割.顯然,G有圈邊割當(dāng)且僅當(dāng)如果G有兩個(gè)可分圈.如果G有一個(gè)圈邊割,那么稱G是圈可分的.對(duì)于一個(gè)圈可分圖G,圈邊連通度cλ(G)定義為所有圈邊割的最小基數(shù)[1].如果G不是圈可分的,那么cλ(G)=∞.

對(duì)于有向圖D,如果D包含兩個(gè)點(diǎn)不交的有向圈,則稱D是圈可分的.令D是一個(gè)圈可分有向圖,S ?A(D),如果D ?S至少有兩個(gè)強(qiáng)連通分支包含有向圈,那么稱S是D的一個(gè)圈弧割.對(duì)于一個(gè)圈可分有向圖D,圈弧連通度λc(D)定義為所有圈弧割的最小基數(shù)[2].如果D不是圈可分的,那么λc(D)=∞.圈邊(弧)連通度的概念可以追溯到1880年Tait著名的錯(cuò)誤猜想[3],該猜想聲稱每一個(gè)3?連通的三正則平面圖都是哈密頓的,從而證明了四色猜想.此后,圈邊(弧)連通度被廣泛應(yīng)用于許多經(jīng)典的圖論領(lǐng)域,如平面圖[4],整數(shù)流猜想[5]等.最近,Zhang和Zhu[2]研究了λc(D1×D2)(其中D1和D2是強(qiáng)連通有向圖),是一個(gè)長(zhǎng)度為ni(1 ≤i ≤k)的有向圈,Wang和Zhang[6]得到了任意圈可分圖的圈邊連通度的上界.關(guān)于圈連通度的更多結(jié)果可參閱文獻(xiàn)[7-9].

在文章中,我們研究了Kautz圖、de Bruijn圖和廣義de Bruijn圖的圈邊(弧)連通度.

1 準(zhǔn)備工作

給定正整數(shù)n和d.Kautz有向圖[10],記為K(d,n)(d ≥1,n ≥1),其中V(K(d,n))={x1x2···xn:xi∈{0,1,···,d},xi+1/=xi,i ∈{1,2,···,n ?1}},而且對(duì)x,y ∈V(K(d,n)),x=x1x2···xn指向y=y1y2···yn當(dāng)且僅當(dāng)對(duì)于i ∈{1,2,···,n?1}滿足xi+1=yi.顯然,K(d,1)是頂點(diǎn)數(shù)為d+1的完全有向圖.Kautz有向圖K(2,2)見(jiàn)圖1.

圖1 Kautz有向圖K(2,2)

無(wú)向Kautz圖UK(d,n)[11]是K(d,n)去掉邊的定向及由此產(chǎn)生的重邊而得到的簡(jiǎn)單圖.當(dāng)d=2,無(wú)向Kautz圖UK(2,n)被稱為無(wú)向二元Kautz圖.無(wú)向Kautz圖UK(2,2)見(jiàn)圖2.對(duì)于d ≥2,n ≥2,UK(d,n)的最小度為2d ?1.顯然,|V(UK(d,n))|=dn+dn?1.K(d,n)中的一對(duì)弧稱為是對(duì)稱的,如果它們有相同的頂點(diǎn)而方向不同.若(x,y)和(y,x)是一對(duì)對(duì)稱弧,為了方便起見(jiàn),我們也稱它們中的一條弧為對(duì)稱弧.UK(d,n)中的一條邊稱為是奇異的,如果這條邊對(duì)應(yīng)著K(d,n) 中的一對(duì)對(duì)稱弧.易知UK(d,n) 中有奇異邊.關(guān)于Kautz有向圖和無(wú)向Kautz 圖的更多結(jié)果可參閱文獻(xiàn)[10-12].

圖2 無(wú)向Kautz圖UK(2,2)

de Bruijn有向圖[10],記為B(d,n) (d ≥2,n ≥2),其中V(B(d,n))={x1x2···xn:xi∈{0,1,···,d ?1},i ∈{1,2,···,n}},對(duì)于x,y ∈V(B(d,n)),x=x1x2···xn指向y=y1y2···yn當(dāng)且僅當(dāng)對(duì)于i ∈{1,2,···,n?1}滿足xi+1=yi.de Bruijn有向圖B(2,2)見(jiàn)圖3.無(wú)向de Bruijn圖UB(d,n)[13]是B(d,n)去掉自環(huán)和邊的定向及由此產(chǎn)生的重邊而得到的簡(jiǎn)單圖.顯然,對(duì)于n ≥2,Kautz有向圖K(d,n)是B(d+1,n)去掉所有對(duì)于某個(gè)i滿足xi=xi+1的點(diǎn)x1x2···xn得到的.無(wú)向de Bruijn圖UB(2,2)見(jiàn)圖4.關(guān)于de Bruijn圖和無(wú)向de Bruijn圖的更多結(jié)果可參閱文獻(xiàn)[10,13,14].廣義de Bruijn有向圖BG(d,n) (d

圖4 無(wú)向de Bruijn圖UB(2,2)

圖5 廣義de Bruijn有向圖BG(2,5)

圖6 無(wú)向廣義de Bruijn圖UBG(2,5)

對(duì)于這里沒(méi)有提到的術(shù)語(yǔ)和符號(hào),可參閱文獻(xiàn)[17].令D是一個(gè)有向圖.對(duì)于頂點(diǎn)x和V(D)的子集H,A+(x)={(x,y) ∈A(D)| y ∈V(D)}和A+(H)={(x,y) ∈A(D)| x ∈H,y ∈V(D ?H)}.令G是一個(gè)無(wú)向圖.對(duì)于頂點(diǎn)x和V(G)的子集H,S(x)={xy |y是x的鄰點(diǎn)}和S(H)={xy|x ∈H,y ∈V(G)H}.對(duì)于V(D)的兩個(gè)子集V1和V2,定義A(V1,V2)={(x,y)|x ∈V1,y ∈V2}.

去掉連通圖G的一個(gè)邊割,若每一個(gè)分支都至少有k個(gè)頂點(diǎn),則稱該邊割為G的一個(gè)k-限制邊割.一個(gè)圖G的k-限制邊連通度λk(G)[18?19]是G的所有的k?限制邊割的最小基數(shù).令[A,B]表示一個(gè)端點(diǎn)在A另一個(gè)端點(diǎn)在B的邊的集合.GA表示把A中所有頂點(diǎn)從G中去掉得到的圖.定義?(A)=|[A,GA]|和ξm(G)=min{?(X):X是G的頂點(diǎn)數(shù)為m 的連通點(diǎn)導(dǎo)出子圖}.眾所周知λ3(G)≤ξ3(G)[12].如果λ3(G)=ξ3(G),則稱圖G為極大3-限制邊連通[20].

引理1[20]當(dāng)n ≥3,無(wú)向二元Kautz圖UK(2,n)是極大3-限制邊連通的(也就是說(shuō)λ3(UK(2,n))=ξ3(UK(2,n))).

引理2[20]令n ≥4,則ξ3(UK(2,n))=6.

引理3令n ≥3,則ξ3(UK(2,n))=6.

證明令F是UK(2,n)中頂點(diǎn)數(shù)為3的連通子圖.如果F是UK(2,n)中的一個(gè)三圈.那么E(F)不包含奇異邊且|S(V(F))|=6.如果F是UK(2,n)中的一條2長(zhǎng)路且E(F)包含一條奇異邊.那么|S(V(F))|=6.如果F是UK(2,n)中的一條2長(zhǎng)路且E(F)不包含一條奇異邊.那么|S(V(F))|=8.通過(guò)ξ3(UK(2,n))的定義,有ξ3(UK(2,n))=6.

引理4[15]當(dāng)n ≥7,無(wú)向二元廣義de Bruijn圖UBG(2,n) 是極大3-限制邊連通的(也就是說(shuō)λ3(UBG(2,n))=ξ3(UBG(2,n))=4).

引理5如果(x,y)是K(d,n)的一對(duì)對(duì)稱弧且(x′,x),(y,y′)∈A(K(d,n)),則(x′,y′)∈A(K(d,n)).

證明令x=x1x2x1x2···,y=x2x1x2x1···,那么x′=αx1x2x1··· (α ∈{0,1,2,···,d}{x1,x2}),y′=x1x2x1···β(β ∈{0,1,2,···,d}{x1,x2}).那么(x′,y′)∈A(K(d,n)).

引理6[21]對(duì)于d ≥2,n ≥2,設(shè)(x,y)和(u,v)是K(d,n)中任兩條不相鄰的弧.如果(x,y)是一條對(duì)稱弧,則K(d,n)中存在2d?2條內(nèi)點(diǎn)不交的從{x,y}到{u,v}的有向路.

引理7[10]B(d,n)是(d?1)-強(qiáng)連通,也就是說(shuō),對(duì)于任不同兩點(diǎn)x,y存在d?1條內(nèi)點(diǎn)不交的(x,y)-路.

引理8[10]BG(d,n)是(d?1)-強(qiáng)連通,也就是說(shuō),對(duì)于任不同兩點(diǎn)x,y存在d?1 條內(nèi)點(diǎn)不交的(x,y)-路.

2 UK(2,n),UB(d,n)和UBG(2,n)的圈邊連通度

2.1 UK(2,n)的圈邊連通度

引理9令d ≥2,n ≥3,則cλ(UK(d,n))≤6d?6.

證明顯然,cλ(UK(2,2))=3.令x,y,z ∈V(UK(d,n)),x=x1x2x3x1x2x3···,y=x2x3x1x2x3x1···,z=x3x1x2x3x1x2···,其中x1/=x2/=x3.那么xyz是UK(d,n)中的一個(gè)三圈.顯然,|S({x,y,z})|=6d ?6.令x′=x3x2x1x3x2x1···,y′=x2x1x3x2x1x3···,z′=x1x3x2x1x3x2···.那么x′y′z′是UK(d,n)?{x,y,z}中的一個(gè)三圈以及S({x,y,z})是UK(d,n)的一個(gè)圈邊割.因此,cλ(UK(d,n))≤6d?6.

引理10令n ≥3,則cλ(UK(2,n))≥6.

證明假設(shè)F是UK(2,n)的一個(gè)最小圈邊割且|F| ≤5,則UK(2,n)?F有兩個(gè)分支包含圈.通過(guò)引理1和3,λ3(UK(2,n))=ξ3(UK(2,n))=6.因?yàn)閨F|<6=λ3(UK(2,n)),所以UK(2,n)?F的一個(gè)分支至多有兩個(gè)頂點(diǎn).這與F是圈邊割矛盾.

通過(guò)引理9和10,得到下面結(jié)果.

定理1令n ≥3,則cλ(UK(2,n))=6.

2.2 UB(d,n)的圈邊連通度

定理2對(duì)于d ≥3,n ≥3,則cλ(UB(d,n))≤6d?6.

證明與引理9的證明相似,得到cλ(UB(d,n))≤6d?6.

2.3 UBG(2,n)的圈邊連通度

引理11如果n ≥8且為偶數(shù),則cλ(UBG(2,n))≤4.

證明因?yàn)轫旤c(diǎn)子集{0,1,和?1,n ?2,n ?1}在V(UBG(2,n))中能導(dǎo)出三圈,其中0是平凡點(diǎn).顯然,S({0,1,是UBG(2,n)的一個(gè)圈邊割,則cλ(UBG(2,n))≤|S({0,1,=4.

引理12如果n ∈{7,9},則cλ(UBG(2,n))≤4.

證明對(duì)于n=7.因?yàn)轫旤c(diǎn)子集{1,2,4}和{3,5,6}在V(UBG(2,n))中能導(dǎo)出三圈,其中2和4是交替點(diǎn).顯然,S({1,2,4})是UBG(2,n)的一個(gè)圈邊割,則cλ(UBG(2,n))≤|S({1,2,4})|=4.

對(duì)于n=9.因?yàn)轫旤c(diǎn)子集{1,2,5}和{3,6,7}在V(UBG(2,n))中能導(dǎo)出三圈,其中2和5是交替點(diǎn).顯然,S({1,2,5})是UBG(2,n)的一個(gè)圈邊割,則cλ(UBG(2,n))≤|S({1,2,5})|=4.

引理13如果n ≥11且為奇數(shù),則cλ(UBG(2,n))≤6.

證明因?yàn)辄c(diǎn)子集{1,2,和?1,n?3,n?2}在V(UBG(2,n))中能導(dǎo)出三圈,則S({1,2,是UBG(2,n)的一個(gè)圈邊割以及cλ(UBG(2,n))≤|S({1,2,=6.

引理14如果n ≥7,則cλ(UBG(2,n))≥4.

證明假設(shè)F是UBG(2,n)的一個(gè)最小圈邊割且|F| ≤3,則UBG(2,n)?F有兩個(gè)分支包含圈.通過(guò)引理4,λ3(UBG(2,n))=ξ3(UBG(2,n))=4.因?yàn)閨F|<4=λ3(UBG(2,n)),所以UBG(2,n)?F的一個(gè)分支至多有兩個(gè)頂點(diǎn).這與F是圈邊割矛盾.

通過(guò)引理11,12,13和14,得到下面結(jié)果.

定理3對(duì)于UBG(2,n),有

(1) 如果n ≥8且為偶數(shù),則cλ(UBG(2,n))=4;

(2) 如果n ∈{7,9},則cλ(UBG(2,n))=4;

(3) 如果n ≥11且為奇數(shù),則4 ≤cλ(UBG(2,n))≤6.

3 K(d,n),B(d,n)和BG(d,n)的圈弧連通度

3.1 K(d,n)的圈弧連通度

引理15

證明因?yàn)镵(2,1)是頂點(diǎn)數(shù)為3的完全有向圖,所以它不是圈可分的.當(dāng)d ≥3,K(d,1)是頂點(diǎn)數(shù)為d+1的完全有向圖.令u,v ∈V(K(d,1)).顯然,A+({u,v})是K(d,1)的一個(gè)圈弧割.那么λc(K(d,1))≤2d?2.令S是K(d,1)的一個(gè)最小圈弧割.因?yàn)镵(d,1)?S有兩個(gè)強(qiáng)連通分支D1和D2包含有向圈,|D1|≥2和|D2|≥2.這就意味著|S|≥2d?2和λc(K(d,1))=|S|≥2d?2.因此,λc(K(d,1))=2d?2.

引理16如果d ≥2,n ≥2,則λc(K(d,n))≤2d?2.

證明令(x,y)是D=K(d,n) (d ≥2,n ≥2)的一條對(duì)稱弧.設(shè)D1=D[{x,y}],D2=D?D1.對(duì)于u,v ∈V(D2),考慮兩種情況.

情況1d=2.因?yàn)棣?D)=d=2,所以D中存在兩條內(nèi)點(diǎn)不交的(u,v)?路P1和P2.如果P1或P2既不包含x也不包含y,那么在D2中有一條(u,v)?路.如果|V(Pi)∩{x,y}|/=?,i ∈{1,2}.在這種情況下設(shè)x ∈V(P1),y ∈V(P2),以及設(shè)(w,x)∈A(P1),(y,z)∈A(P2).通過(guò)引理5,(w,z)∈A(D),且P1包含一條(u,w)-路以及P2包含一條(z,v)-路.因此D2中存在一條(u,v)-路.類似的,D2中存在一條(v,u)?路.因此D2是一個(gè)強(qiáng)連通分支.

情況2d ≥3.因?yàn)棣?D)=d ≥3,所以D中存在d條內(nèi)點(diǎn)不交的(u,v)?路.因此,D2中存在一條(u,v)?路.類似的,D2中存在一條(v,u)?路.因此D2是一個(gè)強(qiáng)連通分支.

顯然,D2包含有向圈.那么A+({x,y})=2d?2是D的一個(gè)圈弧割.因此,如果d ≥2,n ≥2,則λc(K(d,n))≤2d?2.

引理17如果d ≥2,n ≥2,則λc(K(d,n))≥2d?2.

證明令D=K(d,n),S ?A(D)是D的一個(gè)最小圈邊割,有|S|=λc(D).因此,V(D)分為兩個(gè)不交的頂點(diǎn)子集V1和V2且S=A(V1,V2).通過(guò)S的定義,有|V1|≥2,|V2|≥2.因?yàn)镈中有對(duì)對(duì)稱弧且>2d ?2,所以D[V1]或D[V2]中至少包含一條對(duì)稱弧.通過(guò)引理6,|S|≥2d?2.因此,λc(D)=|S|≥2d?2.

通過(guò)引理15,16和17,得到下面結(jié)果.

定理4如果d ≥3,n=1或者d ≥2,n ≥2,則λc(K(d,n))=2d?2.

3.2 B(d,n)的圈弧連通度

定理5如果d ≥2,n ≥2,則λc(B(d,n))=d?1.

證明令x是B(d,n)中的頂點(diǎn)，并且有(x,x) ∈A(B(d,n)).那么A+({x})是B(d,n)中的一個(gè)圈弧割.顯然,λc(B(d,n))≤|A+({x})|=d?1.

另一方面,令S ?A(B(d,n))是B(d,n)的一個(gè)最小圈弧割.則|S|=λc(B(d,n))以及V(B(d,n))分為兩個(gè)不交的頂點(diǎn)子集V1和V2且S=A(V1,V2).因?yàn)樽原h(huán)是一長(zhǎng)的有向圈,|V1| ≥1,|V2| ≥1.通過(guò)引理7,有|S| ≥d ?1和λc(B(d,n))=|S|≥d?1.因此,λc(B(d,n))=d?1.

3.3 BG(d,n)的圈弧連通度

定理6如果d ≥2,n ≥2,則λc(BG(d,n))=d?1.

證明令x是BG(d,n)中的平凡點(diǎn),那么A+({x})是BG(d,n)的一個(gè)圈弧割,則λc(BG(d,n))≤|A+({x})|=d?1.

另一方面,令S ?A(BG(d,n))是BG(d,n)的一個(gè)最小圈弧割,則|S|=λc(BG(d,n))以及V(BG(d,n))分為兩個(gè)不交的頂點(diǎn)子集V1和V2且S=A(V1,V2).因?yàn)樽原h(huán)是一長(zhǎng)的有向圈,|V1| ≥1,|V2| ≥1.通過(guò)引理8,有|S| ≥d?1和λc(BG(d,n))=|S|≥d?1.因此,λc(BG(d,n))=d?1.

4 結(jié)論

在這篇文章中,我們得到如果n ≥3,則cλ(UK(2,n))=6;如果d ≥3,n ≥3,則cλ(UB(d,n)) ≤6d ?6;如果n ∈{7,9}或n ≥8且為偶數(shù),則cλ(UBG(2,n))=4;如果n ≥11且為奇數(shù),且4 ≤cλ(UBG(2,n))≤6;如果d ≥3,n=1或d ≥2,n ≥2,則λc(K(d,n))=2d ?2;如果d ≥2,n ≥2,則λc(B(d,n))=d ?1;如果d ≥2,n ≥2,則λc(BG(d,n))=d?1.在將來(lái)的研究中,可以探討Kautz圖、de Bruijn圖和廣義de Bruijn圖的圈點(diǎn)連通度,以及其它網(wǎng)絡(luò)模型的圈邊連通度和圈弧連通度.