广义b-基超立方体网络的控制数

控制数是刻画容错网络中资源共享可靠性的一个参数。确定网络的控制数是NPC问题。Lakshmivarahan, Dhall提出了著名的互连网络—广义b-基超立方体网络。该文给出了当bn3,2,3,4==时广义b-基超立方体网络控制数的具体值，以及当n58≤≤时控制数的界；进一步提出了两个问题和与该问题相对应的两个猜想。

互连网络是超级计算机的重要组成部分。互连网络可以模型化为一个图。图的顶点表示系统中的处理机，图的边表示处理机之间的通信链路，其中有向边表示单工通信链路，无向边表示半双工通信链路[1]。该文中讨论的是无向图。各种已有互连网络参见[1]-[15]。广义b-基超立方体网络是一种特殊的凯莱图，由Lakshmivarahan 和Dhall [2]中提出，因广义b-基超立方体网络有简单对称正则的结构而被研究。

广义b-基超立方体网络是超立方体网络的推广， 在很多性质方面优于超立方体网络， 例如直径， 连通性， 容错直径等[3]。

图的控制理论是图论的重要分支，美国图论学者W. T. Haynes 等[16]在1998 年出版的专著较为系统地综述了这一领域的一些重要研究成果。尤其在图的点控制方面，提出了多种控制概念。事实上，我们在研究网络的各种控制数时，总是将该网络的一些基本参数(如顶点数，度，直径等)相联系。该文其余结构如下，第二节，给出相关的定义；第三节，给出当3, 2,3,4bn==时广义b-基超立方体网络控制数的具体值，以及当58n≤≤时控制数的界，进一步提出了两个问题和两个猜想；第四节，结束语。

2. 预备知识 定义1 [17]：设2b ≥, 1n ≥，其中, b n 都是整数。定义 (){}9, 1, , 11,0111ij jjbjbkknibΩ=++−= +≤≤−≤≤−且 ( )( )1nnbGCbGCbK−=× ( )nGCb 表示由9Ω生成的凯莱图， 并且( )1GCb 同构于bK ， bK 是具有b 个顶点的完全图。

在这里“× ”表示标准的笛卡尔积运算。

显然，广义b-基超立方体网络是2 元超立方体的一种推广。

定义 () ()()()(){}121 2122111201,1niiibnjCbbbbnbnbnbibjn=++−+−+≤≤−≤≤ 置换bnC 的子群由9Ω生成。

设{}0,1, , 1bb∑=−，定义一个编码 ():nbbnbfC→∑ ()(()()(()) )121 21 21221112niiibnfbbbbnbnbnbi ii++−+−+= 因此，我们将( )(), nGCbV E=表示为n 维b-基超立方体。