冒泡排序图的条件容错哈密尔顿性  

Conditional Fault-Tolerant Hamiltonicity of Bubble-Sort Graphs

作　　者：师海忠[1] 牛攀峰[1] 

机构地区：[1]西北师范大学数学与统计学院,兰州730070

出　　处：《西南大学学报（自然科学版）》2012年第12期97-100,共4页Journal of Southwest University(Natural Science Edition)

基　　金：国家自然科学基金资助项目(10771091);甘肃省自然科学基金(ZS991-A25-017-G)

摘　　要：冒泡排序图是由凯莱图模型设计出来的重要的互连网络.容错性的研究对考察网络的可靠性是十分重要的.n维冒泡排序图Bn是正则对称图,若它有n!个顶点和(n-1)n!/2条边.设F是冒泡排序图Bn的失灵边集,且|F|≤2n-7,若冒泡排序图Bn的每个顶点都至少关联2条非失灵边,那么Bn-F中存在哈密尔顿圈.Bubble sort graphs are important interconnection networks designed from the Cayley graph mod- el. Fault tolerance is very important for measuring reliability of an interconnection network. An n-dimen-sional bubble-sort graph is regular and symmetric, if it has n! nodes and （n-1）n!/2edges. In this paper,we show that if an n-dimensional bubble-sort graph has at most 2n-7 faulty edges, in which each node is incident to at least two non-faulty edges, then Bn-F has a hamiltonian cycle.

关 键 词：容错性 哈密尔顿性 冒泡排序图 互连网络 

分 类 号：O157.6[理学—数学] TP393[理学—基础数学]