关于局部扭立方体的反馈数

确定一般网络(或图)的最小反馈点集问题属NP难问题.n维局部扭立方体网络Qltn是n维超立方体网络Qn的变形且是一类重要的互连网络拓扑结构,其拥有的某些性质优于Qn.根据Qltn顶点集合中最后一位字节不同的特点,将其顶点集合划分为两个不相交的子集,通过构造极大无圈子图得到反馈数的上界,并证明了对任意正整数n≥2,存在常数c∈(0,1)使得反馈数为f(n)=2n-1(1-c/(n-1)).     

折叠立方体网络Qfn Laplace矩阵的谱

图G的Laplace矩阵的谱是由L(G)的所有特征值构成的.研究了一类重要的互连网络拓扑结构折叠立方体网络Qfn的Laplace矩阵的谱.由于折叠立方体Qfn是在超立方体Qn的基础上增加了互补边形成的,利用从Qn的Laplace矩阵An构造Qfn的Laplace矩阵Bn的对偶矩阵Cn=An-I*n+In的方法,确定了Bn和Cn的关系为︱Bn+1︱=︱Bn ︱︱Cn-4In︱,从而确定了折叠立方体的Laplace矩阵Bn的谱.     

超立方体的边可区别数

针对图(点)可区别数,提出了图的边可区别数,给出了n阶路Pn和n阶圈Cn的边可区别数;根据n维超立方体Hn及其p次幂Hpn的结构特性,对n维超立方体Hn和n维超立方体p(＞2)次幂Hpn的边可区别数进行了研究,得到了n维超立方体及其高次幂Hpn的边可区别数的一个上界.即,当n=2时,H2的边可区别数为3;当n≥3时,Hn的边可区别数为2;当n≥4,n≥p＞2时,Hpn的边可区别数小于等于3.     

折叠超立方体网络的t/k诊断问题

为提高系统故障诊断的诊断度,Somani 和Peleg提出了t/k诊断故障策略. n维折叠超立方体网络是具有2n个顶点,(n+1)2n-1条边的(n+1)-维正则图,它是n维超立方体网络增加2n-1补边得到的.中证明了当n≥6和1≤k≤n+1时n维超立方体网络是t/k可诊断的,其中t=(k+1)(n+1)-1/2(k+1)(k+2)+1.     

Cayley图的笛卡尔乘积

Cayley图是由有限群导出的一类重要的高对称正则图,被认为是非常合适的互连网络拓扑结构。百笛卡尔乘积则是从小规模的指定网络构造大规模网络的重要构造方法。本文证明了Cayley图的笛卡尔乘积仍是Cayley图。作为实例,指明循环网络、超立方体、广义超立方体、超环面和立方连通圈等都是Cayley图。这样可以借助于代数方法来分析和研究这些网络的性质。     

超立方体网络广播容错路由算法

研究了具有大量错误结点的超立方体网络中的广播容错路由算法.假定Hn是一个局部3维子立方体连通的n维超立方体网络,并且每一个基本的3维子立方体中分别最多有1个和2个错误结点,从理论上证明了在最坏情况下基于shouting广播通信模式的广播容错路由算法分别经过最多1.5(n-1)和2(n-1)时间步,就可以将源结点的信息广播到Hn中的所有正确结点中;通过实验验证了在均匀和独立的错误结点分布情况下广播时间步的上界实际上只有n+1,支持了理论分析结果.     

在超立方体Qn中通过给定三条边的所有圈

本文研究了在超立方体Qn中通过给定三条边的所有圈的问题．证明了：设E0包含E（Qn）且｜E0｜=3≤n．由E0导出的子图是线性森林，则在Qn中E0的所有边包含在长为l的偶圈中，其中l是满足2n＋2≤l≤2^n的每个偶数．并且下界2n＋2是最优的．     

折叠超立方体网络的边容错哈密顿性

证明了在至多具有2n-3条故障边的n维（n≥3）折叠超立方体网络中,如果每个顶点至少与两条非故障边相邻,则存在一个不含故障边的哈密顿圈.这个界是最好的.     

折叠交叉超立方体的2-额外连通度和2-额外边连通度

有各种各样的方法去衡量不同网络的可靠性和容错性.一个连通图G的g-额外连通度Kg(g-额外边连通度λg)是顶点数最小的顶点集S(边数最少的边集S),使得G-S不连通,并且剩下的每个连通分支含有的顶点数至少是g+1.探究n-维折叠交叉超立方体FCQn的2-额外连通度和2-额外边连通度,证明得到如下结论:当n≥8时,κ2(...     

扭立方体连接网络的结构

提出了一种由３维扭立方体生成的新的互连网络－扭立方体连接网络,它是超立方体的一个变种,主要讨论它的递归结构及其子图的邻接关系。     

交换折叠超立方体的连通度

P.K.K.Loh等人从超立方体Qn中系统地移除了一些边后获得了交换超立方体EH(s,t)。李等人在EH(s,t)的基础上增加了一些边获得了一个新的互联网络交换折叠超立方体EH(s,t)。连通度是衡量网络容错性的一个重要参数,并且连通度越大网络越可靠。本文证明了EH(s,t)的连通度等于其最小度。     

折叠超立方体的谱

通过分析折叠超立方体的结构,得到了折叠超立方体的谱及其Laplace矩阵的谱.     

超立方图和超立方有向图的同构因子分解

图Ｇ＝（Ｖ，Ｅ）的一个同构因子分解是边集Ｅ的一个划分：｛Ｅ１，Ｅ２，…，Ｅｔ｝，使得生成子图（Ｖ， Ｅ１），…，（Ｖ，Ｅｔ）都彼此同构。若 Ｈ≌（Ｖ，Ｅ１），记为 Ｈ［Ｇ或 ｔ］Ｇ．若对每个ｔ≥２．当　　　时．均有：ｔＧ，则称Ｇ为有理图．文章证明了超立方图（ｈｙｐｅｒｃｕｂｅ）和超立方有向图都是有理图．     

超立方体网络递归结构的性质及应用

讨论超立方体结构的递归分解结构及性质,运用这种分解可为并行算法分析和设计提供较好的框架和理论基础,特别适用于递归算法的设计和分析。     

关于超立方体与M（o）bius立方体的连接

新型并行计算系统的研制依赖于对新型互连网络结构及其性质的研究.超立方体及其变型--M（o）bius立方体两者都具有优点,也具有缺点.本文给出了在超立方体与M（o）bius立方体的顶点之间的一种连接,从而得到一种称为HMm-立方体的新型网络,证明了HMm-立方体不仅保持了超立方体和M（o）bius立方体的低顶点度数和高连通度以及其直径至多比M（o）bius立方体大2的性质,而且它克服了超立方体对圈模拟能力的不足.     

超立方体的群连通度

为更好地研究网络拓扑性质,以超立方体为研究对象,使用收缩法给出了超立方体群连通的一个上界,拓展了已有文献中的结果。     

关于Qn的可观测性

文献[3]中给出了当2≤n≤5时，n维立方图Qn的可观测性obs(Qn)的值．本文给出当6≤n≤11时，Qn的obs(Qn)的值，并提出一个关于obs(Qn)值的猜想。     

Star网络的限制边连通度

Star网络被认为是超立方体网络的良好替代.而限制边连通度作为传统边连通度的推广是互连网络容错性的一个重要度量.通过考察一些Star网络的拓扑性质,证明了当n≥4时,它的限制边连通度是2n-4.     

广义超立方体的点扩张

通过广义超立方体的一种点扩张方法构造了广义超立方体循环网络，它包括了人们熟悉的带环连通立方体；证明了广义超立方体循环网络是Cayley图。