有向Kautz图的超级限制弧连通性

林上为，原牡丹，李春芳

(山西大学 数学科学学院，山西 太原 030006)

多处理机系统互连网络的数学模型是图.Kautz图[1]作为Kautz网络的拓扑结构在1969年被提出.由于具有在某种意义下使得连通度达到最大(可靠性到达最高)、直径达到最小(传输延迟达到最小)的优点， Kautz图成为大型多处理机系统重要的候选互连网络，得到广泛的关注[2-4].

边连通度是度量网络可靠性的一个重要参数.为了更加精确地度量，在1988年，Esfahanian和 Hakimi[5]提出了无向图的限制边连通度的概念.关于无向图的限制边连通度已经有很多结果，详见综述文章[6].作为限制边连通度在有向图中的4个推广，强限制弧连通度、限制弧连通度、圈分离弧连通度和条件弧连通度分别被Xu等[7]、Volkmann[8]、Zhang等[9]和周等[10]提出.与无向图的限制边连通度相比，对有向图的限制弧连通度的研究刚刚起步[7-12].

无向Kautz图的限制边连通度已经被完全确定[13-16].有向Kautz图的限制弧连通度也得到了一些研究.2004年，范等[17]确定了有向Kautz图的强限制弧连通度.2017年，周等[10]确定了有向Kautz图的条件弧连通度.文中将完全确定有向Kautz图的限制弧连通度和圈分离弧连通度，并且确定了对应的最小限制弧割的结构特征.

1 准备工作

对于本文没有定义的符号和术语，请参见文[18].先介绍有向Kautz图的定义.

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

下面介绍有向Kautz图K(d,n)的一个有用的性质.称有向Kautz图K(d,n)的一个顶点x=x1x2…xn是交错点，如果存在2个不同的数a,b∈{0,1,…d}，使得x1=x3…=a≠b=x2=x4=….称2个交错顶点x=x1x2…xn和y=y1y2…yn是对称的，如果x1=y2且x2=y1.将长度为2的圈称为2-圈.

命题1[16]xyx是K(d,n)中的一个2-圈当且仅当x,y是一对对称交错点.

无向Kautz图UK(d,n)是有向Kautz图K(d,n)的基础无向图，即通过删去K(d,n)的所有的弧的方向以及只保留2-圈中的一条边得到的无向图.图2给出了无向Kautz图UK(2,2)和UK(2,3).

图2 无向图UK(2,2)和UK(2,3)图

一个图称为是平凡的，若它只有一个顶点，否则称它为非平凡的.

定义1[5]设G是一个连通无向图.称G的一个边子集S是G的一个限制边割，若G-S不连通，且G-S的每个连通分支都是非平凡的.若G中存在一个限制边割，则称G是限制边连通的.限制边连通图G的限制边连通度定义为它的一个最小限制边割所包含的边数，记为λ′(G).

对于无向图G的非空顶点子集对X,Y，记X与Y之间的边的集合为[X,Y].由文[19]中引理1.1的证明可得下面的定理.

定理1[19]设G是一个限制边连通的无向图，如果存在V(G)的一个子集X,使得G的2个导出子图G[X]和G[Y]都包含一个非平凡的连通子图，其中Y=V(G)-X，那么[X,Y]包含G的一个限制边割，从而|[X,Y]|≥λ′(G).

定义2[13]称一个连通无向图G是超级限制边连通的，如果G的任意一个最小限制边割S都是某条边的相邻边集，即G-S只有2个连通分支，且其中的一个连通分支只有一条边.

定理2[13]当d=2和n≥3时，无向Kautz图UK(d,n)的限制边连通度为λ′(UK(d,n))=4d-4=4，且UK(d,n)是超级限制边连通的.

定理3[14]当d≥3和n≥2时，无向Kautz图UK(d,n)的限制边连通度为λ′(UK(d,n))=4d-4，且UK(d,n)是超级限制边连通的.

定理4[15]当d≥3和n=1时，无向Kautz图UK(d,n)的限制边连通度为λ′(UK(d,n))=2d-2，且UK(d,n)是超级限制边连通的.

有向图D称为是强连通的，若对D中的任意2个顶点u和v，都存在从u到v和从v到u的有向路.有向图D的极大强连通子图称为D的强连通分支.若D中有t个强连通分支，则可将这t个强连通分支排序为D1,D2,…,Dt，使得当j>i时，没有从Dj到Di的弧，这样的D1,D2,…,Dt叫作D的一个强连通分支无圈序[18].

设D是一个有向图.称D的一个弧子集S是D的一个弧割，若D-S不强连通.有向图D的弧连通度定义为它的一个最小弧割所包含的弧数，记为λ(D).

定理5[20]当d≥1和n≥2时，有向Kautz图K(d,n)的弧连通度λ(K(d,n))=d.

设D是一个强连通有向图.下面给出D的4种限制弧连通度的定义.

定义3[7]称D中的一个弧割S是D的一个强限制弧割，若D-S的每个强连通分支都是非平凡的.若D中存在一个强限制弧割，则称D是λ2-连通的.λ2-连通有向图D的强限制弧连通度定义为D的一个最小强限制弧割所含的弧数，记作λ2(D).

定义4[8]称D中的一个弧割S是D的一个限制弧割，若D-S有一个非平凡强连通分支D′，使得D-V(D′)包含一条弧.若D中存在一个限制弧割，则称D是λ′-连通的.λ′-连通有向图D的限制弧连通度定义为D的一个最小限制弧割所含的弧数，记作λ′(D).

定义5[9]称D中的一个弧割S是D的一个圈分离弧割，若D-S有至少2个非平凡强连通分支.若D中存在一个圈分离弧割，则称D是λc-连通的.λc-连通有向图D的圈弧连通度定义为D的一个最小圈分离弧割所含的弧数，记作λc(D).

定义6[10]称D中的一个弧割S是D的一个条件弧割，若D-S的最小度δ(D-S)≥1，即D的每个顶点在D-S中都有至少一个出邻点和入邻点.若D中存在一个条件弧割，则称D是λ(1)-连通的.λ(1)-连通有向图D的条件弧连通度定义为D的一个最小条件弧割所含的弧数，记作λ(1)(D).

文献[10]说明以上定义的4种弧连通度都是无向图的限制边连通度在有向图的推广，并且研究了它们之间的关系.

定理6[10]若D是一个λ2-连通有向图，则有λ2(D)≥λ(1)(D)≥λc(D)≥λ′(D).

文[10]也给出例子说明了在同一个有向图上，这4种弧连通度的取值可能不同，这就说明了这4个弧连通度确实是不同的图参数.对有向Kautz图有下列结论.

定理7[17]对d≥2,n≥1且(d,n)≠(2,1)，有向Kautz图K(d,n)是λ2-连通的，且K(d,n)的强限制弧连通度λ2(K(d,n))=2d-2.

定理8[10]对d≥2,n≥1且(d,n)≠(2,1)，有向Kautz图K(d,n)是λ(1)-连通的，且K(d,n)的条件弧连通度λ(1)(K(d,n))=2d-2.

在有向图D中，记∂+(X)={(x,y)∈A(D):x∈X,y∉X}，∂-(X)={(x,y)∈A(D):x∉X,y∈X}.若X是单点集合X={x}，也将∂+(X)简写为∂+(x)，将∂-(X)简写为∂-(x).

定理9[21]若D是一个d-正则的有向图，则对D的任意非空顶点子集X⊆V(D)，有|∂+(X)|=|∂-(X)|.

定义7[22]一个λ′-连通的有向图D是超级限制弧连通的，若对D的每一个最小限制弧割S,都存在一条弧(x,y)∈A(D),使得S∈Ωxy={∂+({x,y}),∂-({x,y}),∂-(x)∪∂+(y),∂+(x)∪∂-(y)}.

定理10[22]设D是一个λ′-连通有向图，S是D的一个最小限制弧割.如果D不是超级限制弧连通的，那么存在一个顶点子集X⊆V(D)，使得S=∂+(X)，且诱导子图D[X]和D[V(D)-X]都包含一条弧.

2 主要结果

显然，对任意的n≥1，K(1,n)是2阶完全有向图，K(2,1)是3阶完全有向图，都不是λ′-连通的，下面考虑剩余的情形.

定理11若d≥2和n≥1是满足(d,n)≠(2,1)的2个整数，则有向Kautz图K(d,n)的限制弧连通度λ′(K(d,n))=2d-2，且K(d,n)中的任意一个最小限制弧割S必是某个2-圈的出弧集或入弧集，即存在K(d,n)中的一对对称交错点x和y，使得S=∂+({x,y})或S=∂-({x,y}).

证明根据定理6和定理7，当d≥2和n≥1且满足(d,n)≠(2,1)时，有2d-2=λ2(K(d,n))≥λ(1)(K(d,n))≥λc(K(d,n))≥λ′(K(d,n))，可得

λ′(K(d,n))≤2d-2.

(1)

设S是K(d,n)的一个最小限制弧割，则有|S|=λ′(K(d,n))≤2d-2.分别考虑以下情形，完成证明.

情形1(d,n)=(2,2).

结合(1)式、定理5以及定义4，2=2d-2≥λ′(K(2,2))≥λ(K(2,2))=2.故|S|=λ′(K(2,2)=2d-2=2.

设D1,D2,…,Dt是K(2,2)-S的一个强连通分支无圈序.显然有t≥2.

假设|V(Dt)|=1，则不失一般性可设V(Dt)={01}.由强连通分支无圈序的定义，可知{(01,12),(01,10)}=∂+(V(Dt))⊆S.又因为|S|=2，所以S={(01,12),(01,10)}.由图1容易看出K(2,2)-S只包含2个强连通分支D1和D2，其中V(D2)={01}，D1=K(2,2)-V(D2).因此D1是K(2,2)-S唯一的非平凡强连通分支，但K(2,2)-V(D1)不含弧，与S是限制弧割矛盾.因此，|V(Dt)|≥2.同理可得|V(D1)|≥2.

假设|V(Dt)|≥3且|V(D1)|≥3.由于K(2,2)只有6个顶点，故t=2且|V(D1)|=|V(D2)|=3.从图1容易看出，K(2,2)中3阶强连通子图只有K(2,2)[{01,12,20}]和K(2,2)[{10,21,02}].不失一般性可设Dt=K(2,2)[{01,12,20}].由强连通分支无圈序的定义，∂+(V(Dt))⊆S，故|S|≥|∂+(V(Dt))|=3，与|S|=2矛盾.因此，|V(Dt)|=2或|V(D1)|=2.

若|V(Dt)|=2，则Dt是一个2-圈，由2=|∂+(V(Dt))|≤|S|=2，可得∂+(V(Dt))=S；同理，若|V(D1)|=2，此时D1是一个2-圈且∂-(V(D1))=S.综上，当(d,n)=(2,2)时，K(2,2)中的任意一个最小限制弧割S是某个2-圈的出弧集或入弧集.

情形2d≥2和n≥1且(d,n)≠(2,2).

情形2.1不存在一条弧(x,y)∈A(K(d,n))，使得S∈Ωxy，其中Ωxy的定义参见定义7.

由定义7，K(d,n)不是超级限制弧连通的.根据定理10，存在一个顶点子集X⊆V(K(d,n))，使得S=∂+(X),且诱导子图K(d,n)[X]和K(d,n)[Y]都至少包含一条弧，其中Y=V(K(d,n))-X.记K(d,n)中X与Y之间的2-圈数为c，即c=|{xyx:x∈X,y∈Y,(x,y),(y,x)∈A(K(d,n))}|.

由于K(d,n)是d-正则的，根据定理9，|∂+(X)|=|∂-(X)|.在无向图UK(d,n)中，记X与Y之间的边的集合为[X,Y]，那么有

|[X,Y]|=|∂+(X)|+|∂-(X)|-c=2|∂+(X)|-c=2|S|-c.

(2)

因为K(d,n)的诱导子图K(d,n)[X]和K(d,n)[Y]都至少包含一条弧，所以无向图UK(d,n)的诱导子图UK(d,n)[X]和UK(d,n)[Y]都至少包含一条边.根据定理1， [X,Y]包含UK(d,n)的一个限制边割，从而

|[X,Y]|≥λ′(UK(d,n)).

(3)

当n=1且d≥3时，K(d,n)是d+1阶完全有向图，对任意的2个顶点x,y，都有xyx是一个2-圈，因此有c=|S|.再结合(1)式、(2)式、(3)式和定理4，可得2d-2≥|S|=2|S|-c=|[X,Y]|≥λ′(UK(d,n))=2d-2，即|S|=|[X,Y]|=λ′(UK(d,n))=2d-2.

当d≥2和n≥2且(d,n)≠(2,2)时，结合(1)式、(2)式、(3)式、定理2和定理3可知 4d-4≥2|S|≥2|S|-c=|[X,Y]|≥λ′(UK(d,n))=4d-4，从而有|[X,Y]|=λ′(UK(d,n))和|S|=2d-2.

综上，当d≥2和n≥1且(d,n)≠(2,2)时都有λ′(K(d,n))=|S|=2d-2且|[X,Y]|=λ′(UK(d,n))，又因为[X,Y]包含UK(d,n)的一个限制边割，所以[X,Y]就是UK(d,n)的一个最小限制边割.由定理2、定理3和定理4，UK(d,n)是超级限制边连通的，由定义2可知或者UK(d,n)[X]是一条边或者UK(d,n)[Y]是一条边.若UK(d,n)[X]是一条边，则可设X={x,y}且(x,y)是K(d,n)的一条弧.此时S=∂+(X)=∂+({x,y})∈Ωxy，矛盾.同理，若UK(d,n)[Y]是一条边，则可设Y={x,y}且(x,y)是K(d,n)的一条弧.此时S=∂-(Y)=∂-({x,y})∈Ωxy,矛盾.

情形2.2存在一条弧(x,y)∈A(K(d,n))，使得S∈Ωxy.

由定义，Ωxy={∂+({x,y}),∂-({x,y}),∂-(x)∪∂+(y),∂+(x)∪∂-(y)}.若(y,x)∉A(K(d,n)),则|∂+({x,y})|=d+(x)+d+(y)-1=2d-1，|∂-({x,y})|=d-(x)+d-(y)-1=2d-1，|∂-(x)∪∂+(y)|=d+(y)+d-(x)=2d，|∂+(x)∪∂-(y)|=d+(x)+d-(y)-1=2d-1，因此|S|≥min{d+(x)+d+(y)-1,d-(x)+d-(y)-1,d+(y)+d-(x),d+(x)+d-(y)-1}=2d-1，与(1)式矛盾.因此可得(y,x)∈A(K(d,n)).此时xyx是一个2-圈.当S=∂-(x)∪∂+(y)时，|S|=|∂-(x)∪∂+(y)|=d+(y)+d-(x)-1=2d-1，与(1)式矛盾；当S=∂+(x)∪∂-(y)时，|S|=|∂+(x)∪∂-(y)|=d+(x)+d-(y)-1=2d-1，与(1)式矛盾，故只有S=∂+({x,y})或S=∂-({x,y}).如果S=∂+({x,y})，那么S是2-圈xyx的出弧集且|S|=|∂+({x,y})|=d+(x)+d+(y)-2=2d-2；如果S=∂-({x,y})，那么S是2-圈xyx的入弧集且|S|=|∂-({x,y})|=d-(x)+d-(y)-2=2d-2.定理得证.

由定理11和定义7可得下面的推论1.

推论1若d≥2和n≥1是满足(d,n)≠(2,1)的2个整数，则有向Kautz图K(d,n)是超级限制弧连通的.

推论2若d≥2和n≥1是满足(d,n)≠(2,1)的2个整数，则对有向Kautz图K(d,n)有λ2(K(d,n))=λ(1)(K(d,n))=λc(K(d,n))=λ′(K(d,n))=2d-2，且每个最小强限制弧割、最小条件弧割、最小圈分离弧割和最小限制弧割都是某个2-圈的出弧集或入弧集.

证明根据定理6、定理7和定理11，容易得到 2d-2=λ2(K(d,n))≥λ(1)(K(d,n))≥λc(K(d,n))≥λ′(K(d,n))=2d-2，故有λ2(K(d,n))=λ(1)(K(d,n))=λc(K(d,n))=λ′(K(d,n))=2d-2.设S是K(d,n)的一个最小强限制弧割或最小条件弧割或最小圈分离弧割或最小限制弧割，则|S|=2d-2.由定义3、定义4、定义5和定义6，S也是K(d,n)的一个限制弧割，由定理11，λ′(K(d,n))=2d-2，故S也是K(d,n)的一个最小限制弧割，故S必是某个2-圈的出弧集或入弧集.