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

交叉立方体CQn和交换交叉立方体ECQ(s,t)是计算机系统里常用的2个拓扑结构.CQn中系统地移除了一些边后,获得了交换交叉立方体ECQ(s,t).在ECQ(s,t)的基础上增加了一些边,就获得了一个新的互连网络交换折叠交叉立方体EFCQ(s,t).连通度和超连通度是衡量互连网络可靠性和容错性的2个重要参数.证明了EFCQ(s,t)的连通度和超连通度分别等于其最小度和最小边度.     

折叠交叉超立方体的结构连通度与子结构连通度

连通度是衡量互连网络可靠性和容错性的一个重要参量,结构连通度与子结构连通度是经典连通度的推广。令H是图G的一个连通子图,F是由G中子图组成的集合,如果F中的每一个元素都同构于H(同构于H的连通子图),并且G-F不连通,则称F是G的一个H-结构割(H-子结构割)。图G的H-结构连通度κ(G;H)(H-子结构连通度κs(G;H)是元素最少的H-结构割(H-子结构割)的基数。文章确定了n-维折叠交叉超立方体的Pk结构连通度κ(FCQ_n;P_k)和子结构连通度κs(FCQn;Pk),其中3≤k≤n。     

折叠交叉立方体的2-外边连通度（英文）

g-外边连通度是衡量大型互连网络可靠性和容错性的一个重要参数.设G是连通图且g是非负整数,如果G中存在某种边子集使得G删除这种边子集后得到的图不连通并且每个分支至少有g+1个点,则所有这种边子集中基数最小的边子集的基数称为图G的g-外边连通度,记作λ_g(G).由定义可知λ₀(G)=λ(G)并且λ₁(G)是图G的超边连通度.n维折叠交叉立方体FCQ_n是由交叉立方体CQ_n增加2^n-1条边后所得.证明了λ₂(FCQ_n)=3n-1,n≥5.     

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

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

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

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

折叠超立方体的边邻域连通度

折叠超立方体是最受关注的网络模型之一.设e是图G的一条边, 如果从图G中删掉以e为中心的双星子图,则称e"倒戈".设S为一个边集, 如果S中的边全部倒戈, 若剩下的子图或者不连通, 或者是一个孤立点, 或者是空集, 则称S为G的割边策略.G的最小割边策略所含的边数为边邻域连通度.该文主要证明了折叠超立方体FQn的边邻域连通度为n.     

折叠超立方体的广义3-连通度

设图G是一个连通图,S⊆V(G)。图G的一棵S-斯坦纳树是一棵包含S中所有顶点的树T=(V ',E '),使得S⊆V '。如果连接S的两棵斯坦纳树T和T ',满足E(T)∩E(T ')=且V(T)∩V(T ')=S,则称T和T '是内部不交的。定义κ(S)为图G中内部不相交S-斯坦纳树的最大数目。广义k-连通度(2≤k≤n)定义为κ_k(G)=min{κ(S)|S⊆V(G)且|S|=k},显然,κ₂(G)=κ(G)。证明了κ₃(FQ_n)=n,其中FQ_n是n-维折叠超立方体。     

折叠交叉立方体的1-好邻诊断度

诊断度是多处理器系统互连网络能够诊断的最大故障结点的个数,它是度量多处理器系统故障诊断能力的一个重要参数.2012年,Peng等提出了一种新的诊断方法g-好邻诊断度,它要求每个非故障顶点至少有g个非故障邻点.n-维折叠交叉立方体网络FCQ_n是由交叉立方体网络CQ_n增加2^n-1条边后所得.该文利用1-好邻诊断度作为评价可靠性的重要度量,对折叠交叉立方体网络的可靠性进行分析,得到折叠交叉立方体网络的1-好邻诊断度.证明了在PMC模型与MM^*模型下FCQ_n的1-好邻诊断度分别等于2n+1,n≥5和2n+1,n≥6.     

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

利用2-外连通度作为评价可靠性的重要度量,对交换折叠超立方体网络EFH(s,t)的可靠性进行分析,得到了交换折叠超立方体网络的2-外连通度.证明了EFH(s,t)的2-外连通度等于3s+1(5≤s≤t).这个结果意味着,为了使EFH(s,t)不连通且每个分支都至少包含3个顶点,至少有3s+1个点要同时发生故障.     

超立方体的群连通度

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

交叉超立方体网络的边泛圈性

作为超立方体Qn的变型，在点数和边数都相同的情况下，交叉超立方体CQn有比超立方体更好的性质．在已获证明的CQn包含所有长度(从4到2^n)的圈的基础上，进一步改进了这一结果，证明了CQn中每条边落在所有长度(从4到2^n)的圈中．     

增广立方体的分支连通度

主要证明了当n≥4时,增广立方体AQn的3-分支连通度是4n-6,以及当n≥9时,增广立方体AQn的4-分支连通度是6n-12.     

基于超立方体与交叉立方体的交叉连接的HC-立方体网络

给出了在超立方体与交叉立方体的顶点之间的一种连接——交叉连接,从而得到一种称为HC-立方体的新型网络,证明了HC-立方体不仅保持了超立方体和交叉立方体的低顶点度数和高连通度的优点,而且其直径至多比交叉立方体大2的性质;它克服了超立方体对圈模拟能力的不足。由于这种网络同时包含了超立方体和交叉立方体作为子网络,因此它既能实现超立方体的功能,又能实现交叉立方体的功能。     

超立方体网络的限制边连通性

m-限制边割将连通图分离成阶不小于m的连通分支,图G的最小m-限制边割所含的边数称为图的m-限制边连通度.本文给出了n立方体的m-限制边连通度的表达式,由此推出：当m≤2（n/2）-1或m=2 k≤2n-1（k为任意正整数）时,超立方体Qn是极大m-限制边连通的.     

无向Kautz图的限制性连通度和限制性容错直径

证明直径为ｌ且最小和最大度分别为３和４的无向Ｋａｕｔｚ图具有限制性连通度４，且其限制性容错直径至多ｌ＋１４。     

多元De Bruijn图的限制边连通性

多元De Bruijn图UB(d, n)是De Bruijn网络的拓扑结构, 它具有高效网络应该具备的许多特性, 如短直径、小最大度和多节点. 本文研究无向多元De Bruijn图的的限制边连通性, 证明当n≥4时UB(d, n)是超级限制边连通的, 回答了张克民等人提出的问题.     

限制边连通度的四个推广之间的关系

无向图的限制边连通度是度量网络可靠性的一个重要指标.为将该概念推广到有向图,人们提出限制弧连通度、强限制弧连通度以及圈弧连通度这三个概念.通过给出限制边连通度在有向图的又一推广—条件弧连通度,并讨论这四个推广之间的关系.     

笛卡尔乘积图的限制边连通性

设G是一个极大限制边连通k-正则图,k≥2．论文证明了：如果│G│〉2k且n≥3,那么笛卡尔乘积图Pn×G是超级限制边连通的,除非G包含子图Kk;如果│G│〉k＋1且n≥3,那么Cn×G是超级限制边连通的,除非n=3且G是圈．     

优化正则图的限制边连通性的最小度条件

限制边割将连通图分离成不合孤立点的不连通图，如果最小限制边割只能分离孤立边，则称图G是超级限制边连通的．证明了如果k＞|G|/2 1，那么k正则连通图G是超级限制边连通的，k的下界在一定程度上是不可改进的．