广义超立方体的广义连通度

张倩华，林上为

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

广义超立方体的广义连通度

张倩华，林上为

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

k元n方体是著名的超立方体网络的推广。针对k元n方体的广义3-连通度问题，证明了对任意的整数k≥3和n≥1，k元n方体中存在2n-1棵内部不交的连接任意3个顶点的树。

超立方体；连通度；可靠性；树；路

0 引言

连通度是图论的核心内容之一，广义连通度作为连通度的一个推广，被广泛运用于互连网络中，可用来测量网络的可靠性。近年来，很多图的广义连通度已经得到研究[7-8]。然而，k元n方体的广义连通度研究较少。本文将在k≥3的条件下，确定k元n方体的广义3-连通度。

1 预备知识

V={x1x2…xn:xi∈{0,1,2,…,k-1},i=1,2,…,n}。

定义2[9]给定一个图G和G的顶点子集X，若G-X不连通或平凡，则称X为G的一个顶点割。G的连通度κ(G)是G中最小顶点割的顶点个数。

熟知连通度有如下的等价定义：

定义3[9]对V(G)的每个2元子集S={x,y}，用κ(S)表示G中内部不交的(x,y)-路的最大数目。图G的连通度κ(G)=min{κ(S):S是V(G)的一个2元子集}。

连通的无圈图称为树，路是特殊的树。

注意，κ2(G)=κ(G)，因此，广义连通度是连通度的一个推广。而κn(G)恰恰就是G中边不相交的生成树的最大数目。广义连通度不仅是一个自然的组合度量，而且它在实际应用中也可以激发人们的兴趣。近年来，图的广义连通度已经得到很多研究[9-10]。

定理2[10]n维超立方体Qn的广义3-连通度为n-1，即κ3(Qn)=n-1。

下面的两个引理将在主要结论的证明中用到。

引理1[9]给定图G和G中的一个顶点x。若κ(G)=k，则对G中任意k个顶点y1,y2,…,yk，G都含(x,y1)-路P1，(x,y2)-路P2，…，(x,yk)-路Pk，使得对所有的i≠j有V(Pi)∩V(Pj)={x}。

2 主要定理及其证明