计算机互连网络的拓扑结构是图,图论是设计和分析计算机网络的一个基本而又重要的数学工具.容错直径D<,k>宽直径d<,k>都是度量互连网络可靠性和有效性的重要参数.对于一般的图G,确定它的容错直径D<,k>困难很大,而确定它的宽直径d<,k>却是个NPC问题,因此讨论它们之间的关系显得很重要.对任何k连通图,它的容错直径D<,k>不超过宽直径d<,k>.到目前为止,关于容错直径与宽直径关系的结果很少.该论文证明了:当G为2连通图时,d<,2>≤max{(d-1)D<,2>-d/2-1)+1,D<,2>+1};并给出d=2时d<,2>=D<,2>+1的一个充分必要条件:即d<,2>=3或4且达到d<,2>值的任何两顶点必相邻.设G为3连通图:若d=2,则d<,3>=≤mzx{(D<,2>-1)(D<,3>-1/2D<,2>-1)+1,3D<,3>-5,D<,3>+1};若D<,2>=2,则d<,3>≤max{D<,3>+1,2D<,3>-2};若d≥2,且d<,2>≥3,则d<,3>≤(d-1)[2(D<,2>-1)(D<,3>-1)-d-2]+1.(d,k)独立数α<,d,k>(G)也是分析互连网络性能的一个重要参数.对于任意给定的图G和正整数d、k,确定G的(d,k)独立数问题是一个NPC问题.因此,确定一些特殊图的(d,k)独立数显得很重要,但是到目前为止,我们还没见到任何特殊图的(d,k)独立数的确定.该文确定了k维超立方体网络的(d,k)独立数等于2,如果d=k(≥4)或者d=k-1(≥6);以及α<,d,k-1>(Q<,k>)=α<,d,k>(Q<,k>),其中0≤t≤k-2,1≤d≤k-t-1.