超立方体外边连通度可靠性分析(英文)  

On Reliability of Hypercubes in Terms of Extra Edge-Connectivity

作　　者：张明祖[1] 孟吉翔[1] 田应智[1] 

机构地区：[1]新疆大学数学与系统科学学院,新疆乌鲁木齐830046

出　　处：《新疆大学学报（自然科学版）》2013年第3期253-256,268,共5页Journal of Xinjiang University(Natural Science Edition)

基　　金：supported by NSFC(11171283)

摘　　要：可靠性评估对于多处理系统的设计和维护占据重要的地位.在众多的可靠性评价系统方法中,外边连通度(也称限制性边连通度)是其中重要的一种.对于一个正整数h,如果图G的边集合S,满足G S是不连通的,并且每一个连通分支至少有h个点,则称S是图G的h-外边割.称h-外边割S最小的基数为图G的h-外边连通度,记为λh(G).文章给出了n维超立方体Qn的h-外边连通度λh(Qn),其中正整数n≥7,2n2+1≤h≤2n2+2.Reliability evaluation of systems is important to the design and maintenance of multiprocessor systems. The extra edge-connectivity （ also restricted edge connectivity） is a kind of measure for the reliability of interconnection systems. For a given positive integer h, an edge set S of a connected graph G is called as a h-extra edge-cut, ifG-S is no longer connected, and each component of G- S has at least h vertices. The cardinality of a minimum h-extra edge-cut, is the h-extra edge-connectivity of G, denoted by λh（G）. Let n be a positive integer, n≥ 7. In this paper, we determine the h-extra edge-connectivity of n-dimensional hypercube ,λh（Qn） for 2n≥7,2「n/2」＋1≤h≤2「n/2」＋2.

关 键 词：可靠性 外边连通 限制性边连通度 超立方体 

分 类 号：O157.5[理学—数学]