有遗失边的n维泡型图和修正泡型图在MM^*模型下的局部诊断度  

The Local Diagnosability of n-Dimensional Bubble-Sort Graphs and Modified Bubble-Sort Graphs with Missing Edges under the MM* Model

作　　者：王世英 黄瑜 赵丽娜 窦丰 

机构地区：[1]山西师范大学数学与计算机科学学院,山西 太原

出　　处：《应用数学进展》2022年第2期679-694,共16页Advances in Applied Mathematics

摘　　要：故障诊断问题曾得到了广泛的研究,并且一些著名网络拓扑的可诊断性已被研究。n维泡型图MBn和修正泡型图Bn有许多好的性质。n维修正泡型图是由n维泡型图添加n!/2条边得到的。在这篇文章中,我们首先研究了Bn在MM*模型下的诊断度,证明了Bn即使存在n-3条遗失边仍具有强局部诊断性,并且证明了是n-3最优值。然后,我们研究了MBn在MM*模型下的诊断度,证明了MBn即使存在n-2条遗失边仍具有强局部诊断性,并且证明了n-2是最优值。The problem of fault diagnosis has been discussed widely, and the diagnosability of some famous network topologies has been explorted. The n-dimensional bubble-sort graphs Bn and the n-dimensional modified bubble-sort graphs MBn have many good properties. The n-dimensional modified bubble-sort graph MBn is obtained by adding n!/2 edges to the n-dimensional bubble-sort graph Bn. In this paper, we firstly discuss the diagnosability of Bn, and show that it has the strong local diagnosability property even if there exist missing edges in it under the MM* model, and the result is optimal with respect to the number of missing edges. Then we discuss the diagnosability of MBn, and show that it has the strong local diagnosability property even if there exist n-2 missing edges in it under the MM* model, and the result is optimal with respect to the number of missing edges.

关 键 词：互连网络 局部诊断度 MM^*模型 n维泡型图 n维修正泡型图 

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