谢 歆，项诗景

(1.黄山学院 数学与统计学院，安徽 黄山 245041； 2.华侨大学 数学科学学院，福建 泉州 362021)

本文采用文献[1]中有关图论的术语和记号，用图表示网络.图的直径和连通度被广泛应用到图论中，可靠性和有效性是设计互连网络的重要参数.网络中从点x到点y的距离是指从x到y最短路的边数，图G的直径是任何两顶点间距离的最大数，连通度k(G)是指使得连通图G不连通所需去掉的最少顶点数.

n维无向超环面网C(d1,d2,…,dn)，顶点集为({(x1,x2,…,xn)|0≤xi≤di-1，i=1,2,…,n}.顶点(x1,x2,…,xn)相邻于2n个顶点(x1±1,x2,…,xn),(x1,x2±1,…,xn),… ,(x1,x2,…,xn±1)，这里±为模di(1≤i≤n)同余.n维无向超环面网C(d1,d2,…,dn)具有2n正则和点可迁的性质，连通度为2n，被广泛应用到网络理论中[2-4].

为了刻画实时平行系统网络传输延迟的可靠性，Flandrin等[5]，Hsu等[6]分别定义了图的m宽直径.设图G为m连通图，顶点x到顶点y的宽度为m的距离dm(G;x,y)是指最小数d使得G中存在m条内点不交且长度不超过d的(x,y)路.图G的m宽直径dm(G)是指G中任何顶点x,y宽度为m的距离dm(G;x,y)的最大值.

在m连通图中，Li等[7]定义了参数(l,m)控制数，在某种程度上(l,m)控制数比宽直径更能精确地刻画网络的可靠性.对于m连通图G和给定正整数l, 如果对于G的任一顶点x(不在S中)都存在m条内点不交且长度不超过l的(S,x)路，则称顶点集G的非空真子集S为G的(l,m)控制集.用Sl,m(G)表示G的所有(l,m)控制集集合，定义参数γl,m(G)=min{|S||S∈Sl,m(G)}为G的(l,m)控制数.

(l,m)控制数不仅推广了通常意义下的图的控制数，并且很好地度量了容错网络中的资源共享问题.一个重要而又实际问题是怎么选取(l,m)控制集S使得S中顶点数尽可能少.因此(l,m)控制数和图的其他重要……