折叠交叉立方体的超连通度和交叉立方体的限制性连通度
发布时间：2019-02-11 17:22
【摘要】：G是一个图,h是一个正整数,一个图G的h-限制性连通度(h-限制性边连通度)是使得G删除G中的某个点集(边集)使得G不连通且每个分支中点的度数至少是h的最小点集(边集)的基数.特殊地,1-限制性连通度(1-限制性边连通度)又称为超连通度(超边连通度).h-限制性连通度参数是传统连通度参数的一个广义化,并且它提高了连通度测量的准确性.研究表明如果互联网络有限制性连通度的特性则它是更可靠的并且比其它网络有一个更低的点的容错率.n维超立方体Q_n在平行计算系统当中是最流行的网络之一.n维交叉立方体CQ_n是Q_n的一个变形.张在文章[Folded-crossed hypercube:a complete interconnection network,J.Syst.Archit.47(2002)917-922]中介绍了一个由交叉立方CQ_n增加2n-1条边后得到新的一个网络n维折叠交叉立方体FCQ_n.本文第一部分,我们证明了n维折叠交叉立方体FCQ_n的超连通度和超边连通度都是2n,n≥4.第二部分证明了n维交叉立方体CQ_n的2-和3-限制性连通度分别是4n-8,n≥4和8n-24,n≥5.
[Abstract]:G is a graph, h is a positive integer, The h-restricted connectivity (h-restricted edge connectivity) of a graph G is such that G deletes a set of points (edge sets) in G such that G is disconnected and the degree of the midpoint of each branch is at least the cardinality of the minimum set of points (edge sets) of h. In particular, 1-restricted connectivity (1-restricted edge connectivity) is also called hyperconnectivity (super-edge connectivity). And it improves the accuracy of connectivity measurement. The study shows that if the Internet has restrictive connectivity, it is more reliable and has a lower fault-tolerant rate than other networks. N-dimensional hypercube Qn is the most popular network in parallel computing systems. N-dimensional cross cube CQ_n is a deformation of QS-n. In his paper [Folded-crossed hypercube:a complete interconnection network,J.Syst.Archit.47 (2002) 917-922], Zhang introduced a new network of n-dimensional folded crossed cube FCQ_n., which was obtained by adding 2n-1 edges to the cross cubic CQ_n. In the first part of this paper, we prove that the hyperconnectivity and hyper-edge connectivity of n-dimensional folded crossed cube FCQ_n are both 2nn 鈮，
本文编号：2419937
[Abstract]:G is a graph, h is a positive integer, The h-restricted connectivity (h-restricted edge connectivity) of a graph G is such that G deletes a set of points (edge sets) in G such that G is disconnected and the degree of the midpoint of each branch is at least the cardinality of the minimum set of points (edge sets) of h. In particular, 1-restricted connectivity (1-restricted edge connectivity) is also called hyperconnectivity (super-edge connectivity). And it improves the accuracy of connectivity measurement. The study shows that if the Internet has restrictive connectivity, it is more reliable and has a lower fault-tolerant rate than other networks. N-dimensional hypercube Qn is the most popular network in parallel computing systems. N-dimensional cross cube CQ_n is a deformation of QS-n. In his paper [Folded-crossed hypercube:a complete interconnection network,J.Syst.Archit.47 (2002) 917-922], Zhang introduced a new network of n-dimensional folded crossed cube FCQ_n., which was obtained by adding 2n-1 edges to the cross cubic CQ_n. In the first part of this paper, we prove that the hyperconnectivity and hyper-edge connectivity of n-dimensional folded crossed cube FCQ_n are both 2nn 鈮，
本文编号：2419937
本文链接：https://www.wllwen.com/kejilunwen/yysx/2419937.html
