图的圈边连通度和圈弧连通度∗

朱虹州，孟吉翔

(新疆大学 数学与系统科学学院，新疆 乌鲁木齐 830046)

0 概念

令G=(V(G),E(G))是一个简单图,F是G中的边集,如果G −F不连通且至少有两个分支包含圈,那么称F是G的一个圈边割.显然,G有圈边割当且仅当如果G有两个可分圈.如果G有一个圈边割,那么称G是圈可分的.对于一个圈可分图G,圈边连通度cλ(G)定义为所有圈边割的最小基数[1].如果G不是圈可分的,那么cλ(G)=∞.

对于有向图D,如果D包含两个点不交的有向圈,则称D是圈可分的.令D是一个圈可分有向图,S ⊆A(D),如果D −S至少有两个强连通分支包含有向圈,那么称S是D的一个圈弧割.对于一个圈可分有向图D,圈弧连通度λc(D)定义为所有圈弧割的最小基数[2].如果D不是圈可分的,那么λc(D)=∞.圈边(弧)连通度的概念可以追溯到1880年Tait著名的错误猜想[3],该猜想声称每一个3−连通的三正则平面图都是哈密顿的,从而证明了四色猜想.此后,圈边(弧)连通度被广泛应用于许多经典的图论领域,如平面图[4],整数流猜想[5]等.最近,Zhang和Zhu[2]研究了λc(D1×D2)(其中D1和D2是强连通有向图),是一个长度为ni(1 ≤i ≤k)的有向圈,Wang和Zhang[6]得到了任意圈可分图的圈边连通度的上界.关于圈连通度的更多结果可参阅文献[7-9].

在文章中,我们研究了Kautz图、de Bruijn图和广义de Bruijn图的圈边(弧)连通度.

1 准备工作

给定正整数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}},而且对x,y ∈V(K(d,n)),x=x1x2···xn指向y=y1y2···yn当且仅当对于i ∈{1,2,···,n−1}满足xi+1=yi.显然,K(d,1)是顶点数为d+1的完全有向图.Kautz有向图K(2,2)见图1.

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

无向Kautz图UK(d,n)[11]是K(d,n)去掉边的定向及由此产生的重边而得到的简单图.当d=2,无向Kautz图UK(2,n)被称为无向二元Kautz图.无向Kautz图UK(2,2)见图2.对于d ≥2,n ≥2,UK(d,n)的最小度为2d −1.显然,|V(UK(d,n))|=dn+dn−1.K(d,n)中的一对弧称为是对称的,如果它们有相同的顶点而方向不同.若(x,y)和(y,x)是一对对称弧,为了方便起见,我们也称它们中的一条弧为对称弧.UK(d,n)中的一条边称为是奇异的,如果这条边对应着K(d,n) 中的一对对称弧.易知UK(d,n) 中有奇异边.关于Kautz有向图和无向Kautz 图的更多结果可参阅文献[10-12].

图2 无向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}},对于x,y ∈V(B(d,n)),x=x1x2···xn指向y=y1y2···yn当且仅当对于i ∈{1,2,···,n−1}满足xi+1=yi.de Bruijn有向图B(2,2)见图3.无向de Bruijn图UB(d,n)[13]是B(d,n)去掉自环和边的定向及由此产生的重边而得到的简单图.显然,对于n ≥2,Kautz有向图K(d,n)是B(d+1,n)去掉所有对于某个i满足xi=xi+1的点x1x2···xn得到的.无向de Bruijn图UB(2,2)见图4.关于de Bruijn图和无向de Bruijn图的更多结果可参阅文献[10,13,14].广义de Bruijn有向图BG(d,n) (d

图4 无向de Bruijn图UB(2,2)

图5 广义de Bruijn有向图BG(2,5)

图6 无向广义de Bruijn图UBG(2,5)

对于这里没有提到的术语和符号,可参阅文献[17].令D是一个有向图.对于顶点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是一个无向图.对于顶点x和V(G)的子集H,S(x)={xy |y是x的邻点}和S(H)={xy|x ∈H,y ∈V(G)H}.对于V(D)的两个子集V1和V2,定义A(V1,V2)={(x,y)|x ∈V1,y ∈V2}.

去掉连通图G的一个边割,若每一个分支都至少有k个顶点,则称该边割为G的一个k-限制边割.一个图G的k-限制边连通度λk(G)[18−19]是G的所有的k−限制边割的最小基数.令[A,B]表示一个端点在A另一个端点在B的边的集合.GA表示把A中所有顶点从G中去掉得到的图.定义ϕ(A)=|[A,GA]|和ξm(G)=min{ϕ(X):X是G的顶点数为m 的连通点导出子图}.众所周知λ3(G)≤ξ3(G)[12].如果λ3(G)=ξ3(G),则称图G为极大3-限制边连通[20].

引理1[20]当n ≥3,无向二元Kautz图UK(2,n)是极大3-限制边连通的(也就是说λ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)中顶点数为3的连通子图.如果F是UK(2,n)中的一个三圈.那么E(F)不包含奇异边且|S(V(F))|=6.如果F是UK(2,n)中的一条2长路且E(F)包含一条奇异边.那么|S(V(F))|=6.如果F是UK(2,n)中的一条2长路且E(F)不包含一条奇异边.那么|S(V(F))|=8.通过ξ3(UK(2,n))的定义,有ξ3(UK(2,n))=6.

引理4[15]当n ≥7,无向二元广义de Bruijn图UBG(2,n) 是极大3-限制边连通的(也就是说λ3(UBG(2,n))=ξ3(UBG(2,n))=4).

引理5如果(x,y)是K(d,n)的一对对称弧且(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]对于d ≥2,n ≥2,设(x,y)和(u,v)是K(d,n)中任两条不相邻的弧.如果(x,y)是一条对称弧,则K(d,n)中存在2d−2条内点不交的从{x,y}到{u,v}的有向路.

引理7[10]B(d,n)是(d−1)-强连通,也就是说,对于任不同两点x,y存在d−1条内点不交的(x,y)-路.

引理8[10]BG(d,n)是(d−1)-强连通,也就是说,对于任不同两点x,y存在d−1 条内点不交的(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)中的一个三圈.显然,|S({x,y,z})|=6d −6.令x′=x3x2x1x3x2x1···,y′=x2x1x3x2x1x3···,z′=x1x3x2x1x3x2···.那么x′y′z′是UK(d,n)−{x,y,z}中的一个三圈以及S({x,y,z})是UK(d,n)的一个圈边割.因此,cλ(UK(d,n))≤6d−6.

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

证明假设F是UK(2,n)的一个最小圈边割且|F| ≤5,则UK(2,n)−F有两个分支包含圈.通过引理1和3,λ3(UK(2,n))=ξ3(UK(2,n))=6.因为|F|<6=λ3(UK(2,n)),所以UK(2,n)−F的一个分支至多有两个顶点.这与F是圈边割矛盾.

通过引理9和10,得到下面结果.

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

2.2 UB(d,n)的圈边连通度

定理2对于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且为偶数,则cλ(UBG(2,n))≤4.

证明因为顶点子集{0,1,和−1,n −2,n −1}在V(UBG(2,n))中能导出三圈,其中0是平凡点.显然,S({0,1,是UBG(2,n)的一个圈边割,则cλ(UBG(2,n))≤|S({0,1,=4.

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

证明对于n=7.因为顶点子集{1,2,4}和{3,5,6}在V(UBG(2,n))中能导出三圈,其中2和4是交替点.显然,S({1,2,4})是UBG(2,n)的一个圈边割,则cλ(UBG(2,n))≤|S({1,2,4})|=4.

对于n=9.因为顶点子集{1,2,5}和{3,6,7}在V(UBG(2,n))中能导出三圈,其中2和5是交替点.显然,S({1,2,5})是UBG(2,n)的一个圈边割,则cλ(UBG(2,n))≤|S({1,2,5})|=4.

引理13如果n ≥11且为奇数,则cλ(UBG(2,n))≤6.

证明因为点子集{1,2,和−1,n−3,n−2}在V(UBG(2,n))中能导出三圈,则S({1,2,是UBG(2,n)的一个圈边割以及cλ(UBG(2,n))≤|S({1,2,=6.

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

证明假设F是UBG(2,n)的一个最小圈边割且|F| ≤3,则UBG(2,n)−F有两个分支包含圈.通过引理4,λ3(UBG(2,n))=ξ3(UBG(2,n))=4.因为|F|<4=λ3(UBG(2,n)),所以UBG(2,n)−F的一个分支至多有两个顶点.这与F是圈边割矛盾.

通过引理11,12,13和14,得到下面结果.

定理3对于UBG(2,n),有

(1) 如果n ≥8且为偶数,则cλ(UBG(2,n))=4;

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

(3) 如果n ≥11且为奇数,则4 ≤cλ(UBG(2,n))≤6.

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

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

引理15

证明因为K(2,1)是顶点数为3的完全有向图,所以它不是圈可分的.当d ≥3,K(d,1)是顶点数为d+1的完全有向图.令u,v ∈V(K(d,1)).显然,A+({u,v})是K(d,1)的一个圈弧割.那么λc(K(d,1))≤2d−2.令S是K(d,1)的一个最小圈弧割.因为K(d,1)−S有两个强连通分支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)的一条对称弧.设D1=D[{x,y}],D2=D−D1.对于u,v ∈V(D2),考虑两种情况.

情况1d=2.因为κ(D)=d=2,所以D中存在两条内点不交的(u,v)−路P1和P2.如果P1或P2既不包含x也不包含y,那么在D2中有一条(u,v)−路.如果|V(Pi)∩{x,y}|/=∅,i ∈{1,2}.在这种情况下设x ∈V(P1),y ∈V(P2),以及设(w,x)∈A(P1),(y,z)∈A(P2).通过引理5,(w,z)∈A(D),且P1包含一条(u,w)-路以及P2包含一条(z,v)-路.因此D2中存在一条(u,v)-路.类似的,D2中存在一条(v,u)−路.因此D2是一个强连通分支.

情况2d ≥3.因为κ(D)=d ≥3,所以D中存在d条内点不交的(u,v)−路.因此,D2中存在一条(u,v)−路.类似的,D2中存在一条(v,u)−路.因此D2是一个强连通分支.

显然,D2包含有向圈.那么A+({x,y})=2d−2是D的一个圈弧割.因此,如果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的一个最小圈边割,有|S|=λc(D).因此,V(D)分为两个不交的顶点子集V1和V2且S=A(V1,V2).通过S的定义,有|V1|≥2,|V2|≥2.因为D中有对对称弧且>2d −2,所以D[V1]或D[V2]中至少包含一条对称弧.通过引理6,|S|≥2d−2.因此,λc(D)=|S|≥2d−2.

通过引理15,16和17,得到下面结果.

定理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)中的顶点，并且有(x,x) ∈A(B(d,n)).那么A+({x})是B(d,n)中的一个圈弧割.显然,λc(B(d,n))≤|A+({x})|=d−1.

另一方面,令S ⊆A(B(d,n))是B(d,n)的一个最小圈弧割.则|S|=λc(B(d,n))以及V(B(d,n))分为两个不交的顶点子集V1和V2且S=A(V1,V2).因为自环是一长的有向圈,|V1| ≥1,|V2| ≥1.通过引理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)中的平凡点,那么A+({x})是BG(d,n)的一个圈弧割,则λc(BG(d,n))≤|A+({x})|=d−1.

另一方面,令S ⊆A(BG(d,n))是BG(d,n)的一个最小圈弧割,则|S|=λc(BG(d,n))以及V(BG(d,n))分为两个不交的顶点子集V1和V2且S=A(V1,V2).因为自环是一长的有向圈,|V1| ≥1,|V2| ≥1.通过引理8,有|S| ≥d−1和λc(BG(d,n))=|S|≥d−1.因此,λc(BG(d,n))=d−1.

4 结论

在这篇文章中,我们得到如果n ≥3,则cλ(UK(2,n))=6;如果d ≥3,n ≥3,则cλ(UB(d,n)) ≤6d −6;如果n ∈{7,9}或n ≥8且为偶数,则cλ(UBG(2,n))=4;如果n ≥11且为奇数,且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.在将来的研究中,可以探讨Kautz图、de Bruijn图和广义de Bruijn图的圈点连通度,以及其它网络模型的圈边连通度和圈弧连通度.