朱虹州，孟吉翔

(新疆大学 数学与系统科学学院，新疆 乌鲁木齐 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.对……