折叠交叉立方体的3-额外边连通度

蔡学鹏， 徐刚刚， 史 伟

（新疆农业大学 数理学院，新疆 乌鲁木齐830052）

众所周知，互连网络在并行计算及通信系统中发挥着重要作用.一个网络的拓扑结构在数学上通常被抽象的模型化为一个图G＝（V（G），E（G）），其中V（G）是图G的顶点集，表示网络处理器的集合；E（G）是图G的边集，表示网络的通信链路集.本文中术语图和网络可以互换使用，且所有的图都认为是无向的、简单的和连通的.对于未说明的图论符号和术语，可参考文献［1-2］.

设G＝（V（G），E（G））是一个图，则对于图G中任意顶点u∈V（G），设集合

和

分别表示顶点u的邻点集和邻边集，记为NG（u）和NEG（u）.d G（u）＝ ｜NG（u）｜称为图G中顶点u的度.对于图G的子图K，设

和

分别表示子图K在G中的邻点集和子图K在G中的邻边集.设Kr，s＝ （V1∪V2，E）表示一个完全二部图，其中V1和V2分别是由r个点和s个点构成的不交点集.Kr，s的点集V（Kr，s）＝V1∪V2，边集E＝｛（u，v）｜u∈V1，v∈V2｝.Pn＝ 〈u1，u2，…，u n〉表示图G中一条具有n个顶点和n－1条边的路，Cn表示具有n个顶点的圈.

图G的经典连通度κ（G）和边连通度λ（G）是衡量网络可靠性和容错性的2个重要参数［3］.连通度κ（G）和边连通度λ（G）越大，网络的可靠性就越高，但也有明显的不足之处.比如，在互连网络的实际应用中，与一个处理器相连接的所有处理器（链路）同时发生故障可能性较低，所以这2个参数衡量网络可靠性和容错性是不精确的.为克服这些不足，可以通过对G-S的每一个分支强加一些限制条件来推广图G的经典连通度（边连通度），这里S⊂V（G）（S⊂E（G））.

设P是图G所具有的一种性质.Harary［4］首先提出图G的条件连通度（边连通度）概念.如果G中存在某种点子集（边子集），使得G删……