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

g-额外边连通度是衡量大型互连网络可靠性和容错性的一个重要参数.设G是连通图且g是非负整数,如果图G中存在某种边子集,使得G中删除这种边子集后得到的图不连通并且每个分支的点数超过g,则所有这种边子集中基数最小的边子集的基数称为图G的g-额外边连通度,记作λ_g(G).一个新的网络交换折叠超立方体网络记为EFH(s,t).本文利用2-额外边连通度作为评价可靠性的重要度量,对交换折叠超立方体网络的可靠性进行了分析,得到了交换折叠超立方体网络的2-额外边连通度.证明了:EFH(s,t)的2-额外边连通度等于3s+2(6≤s≤t).这个结果意味着:为了使EFH(s,t)不连通且每个分支都至少包含3个顶点,至少有3s+2条边要同时发生故障.     

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

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

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

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

折叠交叉超立方体的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)的连通度等于其最小度。     

变形超立方体网络的可靠性分析

作为超立方体网络的变形, n维变形超立方体VQ_n是Cheng和Chuang于1994年提出来的,它具有许多超立方体所具有的优良性质, 比如正则性和递归结构.证明了:VQ_n 的连通度和边连通度都等于n,限制连通度和限制边连通度都等于2n-2. 这个结果意味着,为了使VQ_n不连通且不含孤立点, 至少有2n-2个点或者边要同时发生故障.     

折叠交叉立方体的3-额外边连通度

g-额外边连通度是衡量大型互连网络可靠性和容错性的一个重要参数.设G是连通图且g是非负整数,如果G中存在某种边子集使得G删除这种边子集后得到的图不连通,且每个分支至少有g+1个点,则所有这种边子集中基数最小的边子集的基数称为图G的g-额外边连通度,记作λg(G).由定义可知,λ0(G)=λ(G)且λ1(G)是图G的超边...     

折叠交叉立方体的限制连通度

限制性连通度作为评估互联网络容错性的最佳参数之一,在多处理器系统中对可靠性计算起着重要作用.给定一个连通图G=(V,E)和一个非负整数h,子集F?V(G)(F?E(G))(如果存在)称为h-限制点割(h-限制边割),如果G-F不连通,并且G-F中的每个连通分支至少有h+1个顶点,其中最小的h-限制点割(h-限制边割)的基数称为图G的h-限制连通度(h-限制边连通度),记为κh(G)(λh(G)).本文确定了h=2时n-维折叠交叉立方体FCQn的κh(G)和λh(G).     

一类特殊图k-限制边连通度

设F?E (G)为图G=(V,E)的一个边集,如果G-F不连通且G-F的每一个连通分支都至少有k个顶点,F就称为图G的一个k-限制性边割.图G的k-限制边连通度是图G的最小k-限制性边割的基数,记为λk(G).限制性边连通度是衡量网络可靠性的重要参数之一.证明了在2≤k≤n,h≤n/2的情况下,一类特殊图—蜻蜓网络D(n,h)的k-限制边连通度是■     

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

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

折叠超立方体网络的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.     

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

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

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

连通度是衡量互连网络可靠性和容错性的一个重要参量，结构连通度与子结构连通度是经典连通度的推广。令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。     

交换超立方体结构性质的一些注记

交换超立方体EH(s,t)(s≥1,t≥1)作为超立方体的变型结构,是在(s+t+1)维超立方体Qs+t+1的基础上删除一系列的边得到的。交换超立方体EH(s,t)的边数几乎是Qs+t+1边数的一半,它不仅保持了超立方体的许多优良性质,而且实现了网络功能和硬件开销的平衡。本文主要探讨交换超立方体的结构性质,研究交换超立方体EH(s,t)的点传递性问题,给出了EH(s,t)的点之间的传递映射;同时分析了EH(s,t)与EH(t,s)之间的同构关系,并且给出了他们之间的所有同构映射。     

同阶双轨道连通图的超圈边连通性

对于图G,如果G-F是不连通的且至少有两个分支含有圈,则称F为图G的圈边割.如果图G有圈边割,则称其为圈可分的.最小圈边割的基数叫作圈边连通度.如果去除任何一个最小圈边割,总存在一分支为最小圈,则图G为超圈边连通的.设G=(G_1,G_2,(V_1,V_2))为双轨道图,最小度δ(G)≥4,围长g(G)≥6且|V_1|=|V_2|.假设G_i是k_i-正则的,k_1≤k_2且G_1包含一个长度为g的圈,则G是超圈边连通的.     

交换超立方体在PMC模型下的g好邻条件诊断度

诊断度是多处理器系统互连网络能够诊断的最大故障结点的个数,它是度量多处理器系统故障诊断能力的一种参数。g好邻条件诊断度是2012年提出的一种新的诊断度,它要求每个非故障顶点至少有g个非故障邻点。研究了交换超立方体EH(s,t)在PMC模型下的g好邻条件诊断度,证明了EH(s,t)(1≤s≤t,0≤g≤s)在PMC模型下的g好邻条件诊断度为2g(s+2-g)-1.     

点可迁图的限制边连通度

对于度k( ≥ 2 )的点可迁连通图的限制边连通度λ′,已知k≤λ′≤ 2k- 2 ,且λ′的界可以达到 .在此基础上 ,对度为k的点可迁图G进一步给出了满足λ′(G) =k的两个充要条件 .接着 ,对任意的连通图G0 证明了λ′(K2 ×G0 ) =min{2δ (G0 ) ,2λ′(G0 ) ,v(G0 ) }.最后证明了对任意满足 0≤s≤k- 3的整数s,存在度为k的点可迁连通图G满足λ′(G)=k s当且仅当k为奇数或者s为偶数     

某些笛卡尔乘积图的超边连通度

一个连通图称为超边连通的,如果去掉每一个最小边割集后产生一个孤立点。一个超边连通图的超边连通度λ′(G)是指那些去掉后不产生孤立点的边割集的最小基数。考虑笛卡尔乘积图并证明:若对于每一个i=1,2,…,n,Gi是ki(≥1)正则,ki连通图且满足某些给定的条件,则λ′(G1×G2×…×Gn)=2∑from i=1 to n(ki-2)。     

交叉立方体的限制性连通度（英文）

G是一个图,h是一个正整数,一个图G的h-限制性连通度是使得G删除G中的某个点集使得G不连通且每个分支中点的度数至少是h的最小点集的基数.交叉立方体网络是超立方体的一个变形,在平行计算系统当中交叉立方体是最重要的网络之一.该文证明了n维交叉立方体2-和3-限制性连通度分别是4n-8(n≥4)和8n-24(n≥5).     

中国科学技术大学学报 2006年第36卷总目次

数学一些笛卡尔乘积图的限制连通度(英文)……………………………潘向峰,徐俊明,吕敏(3-237)强乘积图的连通度(英文)………………………………………………………孙犁,徐俊明(3-241)折叠超立方体网络的边容错哈密顿性(英文)…………………………马美杰,徐俊明,杜正中(3-244)立方体和折叠立方体的限制边连通度和超边连通度(英文)…………………朱强,徐俊明(3-249)图的边添加和减少(英文)……………………………………………NAJIMAlaa A,徐俊明(3-254)一般T网格上样条空间的维数(英文)………………………………黄章进,邓建松,李新(6-573)…