故障折叠超立方体中的路和圈

本文研究了含故障点的n-维折叠超立方体FQn中的路和圈嵌入的问题,分析了折叠超立方体网络的潜在特性.利用了构造的方法,得到了含2n-3个故障点的折叠超立方体FQn中含长为2n-2f的圈的结论,推广了折叠超立方体网络中1-点容错圈嵌入的结果.     

含故障点的加强超立方体中路和圈的嵌入

本文研究了含故障点的n-维加强超立方体Q_n,k中的路和圈嵌入的问题.充分分析了加强超立方体网络的潜在特性,利用了构造的方法.得到了含2n-4个故障点的加强超立方体Q_n,k中含长为2ⁿ-2f的容错圈的结论,推广了折叠超立方体网络中1-点容错圈嵌入的结果.其中折叠超立方体网络为加强超立方体网络的一种特殊情况.     

故障加强超立方体中的路和圈（英文）

本论文研究了含故障点的加强超立方体中路和圈的嵌入问题.利用数学归纳法,获得了故障加强超立方体中的路和圈,推广了超立方体中点容错路和圈嵌入的结果.     

故障加强超立方体中的路和圈

本论文研究了含故障点的加强超立方体中路和圈的嵌入问题.利用数学归纳法,获得了故障加强超立方体中的路和圈,推广了超立方体中点容错路和圈嵌入的结果.     

变种超方体网络的容错直径与宽直径

研究变种超方体的网络容错直径和宽直径,证明了n维变种超立方体的n-1容错直径和n宽直径为[2n/3]+1或[2n/3]+2.     

n维超立方体中边不交的汉密尔顿圈

n维超立方体在并行计算领域有着广泛的应用,其特殊的拓扑结构对大规模的多处理器系统的性能具有重要的影响.在选择互连网络时,汉密尔顿性是评估网络性能的一个重要指标.本文研究n维超立方体Q_n中的汉密尔顿圈,采用构造的方法证明了以下结论:当n是2的幂次方时,Q_(2n)中有且仅有n个边不交的汉密尔顿圈.     

广义Fibonacci立方体的网络容错性质分析

主要研究广义Fibonacci立方体的容错直径和宽直径,证明了n维Fibonacci立方体网络的k-1容错直径和k宽直径都是n-1,其中k=[n/3].     

纽立方体网络的容错泛圈性

互连网络包含所有可能长度的圈是一个重要的拓扑性质。纽立方体网络TOn是超立方体网络Qn的一种变型,其中n≥3是奇数。Chang等人[Information Science,113(1999),147-167]证明了TOn中包含任意长度为l的圈,其中4≤l≤2n。如果TOn中的故障点数和故障边数之和不超过(n-2),Huang等人[J.Parallel andDistributed Computing,62(2002),591-640]证明了:TQn中包含长度为2n-fv的圈,其中fv是故障点数。这篇文章改进这些结果为:TQn中包含任意长度为l的圈,其中4≤l≤2n-fv。     

折叠立方体网络的最小反馈点集

对简单图G=(V,E),顶点子集F V,如果由V\F导出的子图不含圈,则称F是G的反馈点集。点数最小的反馈点集称图的最小反馈点集,最小的点数称为反馈数。一个k维折叠立方体是由一个k维超立方体加上所有的互补边构成的图。本文证明了k维折叠立方体网络的反馈数f(k)=c.2k-1(k 2),其中c∈k-1     

广义超立方体网络中一类容错路由选择

证明了n-维广义超立方体网络Q(m1,m2,…,mn)中,任意两个节点x和y之间存在长度均不超过H(x,y)+2的m1+m2+…+mn-n条内点不交的路由,其中有H(x,y)条长度不超过H(x,y),此处H(x,y)表示x到y的汉明距离.并在此基础上讨论了广义超立方体网络的容错路由问题.证明了即使无效点很多,但只要存在某个(n-1)-维广义超子立方体中无效节点较少,则该n-维广义超立方体中的任意两个有效节点之间可以找到最优路由或接近最优路由的有效路由.     

ON THE CONDITIONAL EDGE CONNECTIVITY OF ENHANCED HYPERCUBE NETWORKS

Let G =(V, E) be a connected graph and m be a positive integer, the conditional edge connectivity λ_δ~m is the minimum cardinality of a set of edges,if it exists, whose deletion disconnects G and leaves each remaining component with minimum degree δ no less than m. This study shows that λ_δ~1(Q_(n,k)) = 2 n,λ_δ~2(Q_(n,k)) = 4 n-4(2 ≤ k ≤ n-1, n ≥ 3) for n-dimensional enhanced hypercube Q_(n,k). Meanwhile, another easy proof about λ_δ~2(Q_n) = 4 n-8, for n ≥ 3 is proposed. The results of enhanced hypercube include the cases of folded hypercube.     

互连网络的向量图模型

n-超立方体,环网,k元n超立方体,Star网络,煎饼(pancake)网络,冒泡排序(bubble sort)网络,对换树的Cayley图,De Bruijn图,Kautz图,Consecutive-d有向图,循环图以及有向环图等已被广泛的应用做处理机或通信互连网络.这些网络的性能通常通过它们的度,直径,连通度,hamiltonian性,容错度以及路由选择算法等来度量.在本文中,首先,我们提出了有向向量图和向量图的概念;其次,我们开发了有向向量图模型和向量图模型来更好地设计,分析,改良互连网络;我们进一步证明了上述各类著名互连网络都可表示为有向向量图模型或向量图模型;更重要的是该模型能够使我们设计出了新的互连网络---双星网络和三角形网络.     

折叠交叉立方体的分支边连通度

r-分支连通度(边连通度)是衡量大型互连网络可靠性和容错性的一个重要参数.设G是连通图且r是非负整数,如果G中存在某种点子集(边子集)使得G删除这种点子集(边子集)后得到的图至少有r个连通分支.则所有这种点子集(边子集)中基数最小的点子集(边子集)的基数称为图G的r-分支连通度(边连通度).n-维折叠交叉立方体FCQn是由交叉立方体CQn增加2n-1条边后所得.该文利用r-分支边连通度作为可靠性的重要度量,对折叠交叉立方体网络的可靠性进行分析,得到了折叠交叉立方体网络的2-分支边连通度,3-分支边连通度,4分支边连通度.确定了折叠交叉立方体FCQn的r-分支边连通度.     

两类网络的2-限制连通度

给定图G=(V,E)和非负整数h,图G的h-限制点割S是V(G)的一个子集(如果存在)使得G-S不连通且G-S中任一点的度数至少为h.图G的h-限制连通度κ~h(G)是G的最小h-限制点割的阶数.本文中,我们证明了κ~2(FCQ_n)=4n-4 (n≥8),κ~2(SQn)=4n-8(n≥4),其中FCQ_n和SQ_n分别是n维折叠交叉超立方体和n维spined cube.     

故障超立方体中经过指定路的无故障圈

研究了在含有故障点和（或）故障边的n维超立方体Qn中经过给定路的无故障圈问题,得到以下结果：设Fv V（Qn）,Fe E（Qn）.若｜Fv｜＋｜Fe｜≤n-h且3≤h≤n,或｜Fv｜＋｜Fe｜≤n-3且h=2,则在Qn-Fv-Fe中,每一条长度等于h的路P都包含在每个偶长度从2h＋2到2^n-2｜Fv｜的圈中.并且若又有条件｜Fv｜＋｜Fe｜〈h-1时,则路P还包含在长度等于2h的无故障的圈中.     

超立方体网络的(d,k)控制数

(d,k)控制数是刻画容错网络中资源共亨可靠性的一个新参数.本文考虑了k维超立方体Qk的(d,k)控制数,得到:γ1,k(Qk)=2k-1(k>1);d=[k/2] 1(k>2)时,γd,k(Qk)=2;d≤[k/2](k≥4)时,3≤γd,k(Qk)≤2k-d 1;以及若d为正整数,且[k/d]=[k/(d-1)] 1,则γd,k(Qk)=γd,k(Qk),其中[k/d].d 1≤k1≤k.     

关于Weichsel猜想的一点注记

设P是n-立方体图Q_n的完备控制集．在1994年,Weichsel证明了存在某些整数r_1,r_2,…,r_m使P在Q n中的诱导子图〈P〉为Q_(r1),Q_(r2),…,Q_(rm)的不交之并,并且猜想r_1=r_2=…=r_m．本文证明了当m≤20时,该猜想正确．     

变更图的直径

P(t,n)和C(t,n)分别表示在阶为n的路和圈中添加t条边后得到的图的最小直径；f(t,k)表示从直径为k的图中删去t条边后得到的连通图的最大直径．这篇文章证明了t≥4且n≥5时,P(t,n)≤(n-8)/(t 1) 3；若t为奇数,则C(t,n)≤(n-8)/(t 1) 3；若t为偶数,则C(t,n)≤(n-7)/(t 2) 3．特别地,「(n-1)/5」≤P(4,n)≤「(n 3)/5」,「n/4」-1≤C(3,n)≤「n/4」．最后,证明了：若k≥3且为奇数,则f(t,k)≥(t 1)k-2t 4．这些改进了某些已知结果．     

半群O_n(k)的秩

设O_n是有限链[n]上的保序变换半群.对任意1≤k≤n-1,研究半群O_n(k)={α∈O_n:(x∈[n]x≤k→xα≤k}的秩和幂等元秩,证明了半群O_n(k)的秩为2n-3.进一步,得到了半群O_n(k)(2≤k≤n-1)的幂等元秩为n和半群O_n(1)的幂等元秩为n-1.     

关于Mbius立方体网格的连通度(英文)

图的连通度、超连通性和限制连通度是度量互连网络容错性的重要参数 .该文考虑n维M bius立方体网络MQn,证明了它的点和边连通度都为n ,当n是任何正整数时它是超连通的 ,当n≠ 2时它是超边连通的 ,当n≥ 3时它的限制点连通度和当n≥ 2时的限制边连通度都为 2n- 2 .