有遗失边的n维泡型图和修正泡型图在MM*模型下的局部诊断度
The Local Diagnosability of n-Dimensional Bubble-Sort Graphs and Modified Bubble-Sort Graphs with Missing Edges under the MM* Model
摘要: 故障诊断问题曾得到了广泛的研究，并且一些著名网络拓扑的可诊断性已被研究。n维泡型图MBn和修正泡型图Bn有许多好的性质。n维修正泡型图是由n维泡型图添加n!/2条边得到的。在这篇文章中，我们首先研究了Bn在MM*模型下的诊断度，证明了Bn即使存在n-3条遗失边仍具有强局部诊断性，并且证明了是n-3最优值。然后，我们研究了MBn在MM*模型下的诊断度，证明了MBn即使存在n-2条遗失边仍具有强局部诊断性，并且证明了n-2是最优值。
Abstract: 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.
文章引用：王世英, 黄瑜, 赵丽娜, 窦丰. 有遗失边的n维泡型图和修正泡型图在MM*模型下的局部诊断度[J]. 应用数学进展, 2022, 11(2): 679-694. https://doi.org/10.12677/AAM.2022.112075

参考文献

[1] Dahbura, A.T. and Masson, G.M. (1984) An Fault Identification Algorithm for Diagnosable Systems. IEEE Transactions on Computers, 33, 486-492. [Google Scholar] [CrossRef] 
[2] Fan, J. (2002) Diagnosability of Crossed Cubes under the Comparison Diagnosis Model. IEEE Transactions on Parallel and Distributed Systems, 13, 1099-1104. [Google Scholar] [CrossRef] 
[3] Lai, P.L., Tan, J.J.M., Chang, C.P. and Hsu, L.H. (2005) Conditional Diagnosability Measures for Large Multiprocessor Systems. IEEE Transactions on Computers, 54, 165-175. [Google Scholar] [CrossRef] 
[4] Maeng, J. and Malek, M. (1981) A Comparison Connection Assignment for Self-Diagnosis of Multiprocessors System. Proceeding of the 11th International Symposium on Fault-Tolerant Computing, 11, 173-175.
[5] Sengupta, A. and Dahbura, A.T. (1992) On Self-Diagnosable Multiprocessor Systems: Diagnosis by the Comparison Approach. IEEE Transactions on Computers, 41, 1386-1396. [Google Scholar] [CrossRef] 
[6] Hsu, G.H. and Tan, J.J.M. (2007) A Local Diagnosability Measure for Multiprocessor Systems. IEEE Transactions on Parallel and Distributed Systems, 18, 598-607. [Google Scholar] [CrossRef] 
[7] Chiang, C.F. and Tan, J.J.M. (2009) Using Node Diagnosability to Determine t-Ddiagnosability under the Comparison Diagnosis Model. IEEE Transactions on Computers, 58, 251-259. [Google Scholar] [CrossRef] 
[8] Chiang, C.F., Hsu, G.H., Shih, L.M. and Tan, J.J.M. (2012) Diagnosability of Star Graphs with Missing Edges. Information Sciences, 188, 253-259. [Google Scholar] [CrossRef] 
[9] Cheng, E. and Lipták, L. (2013) Dignosability of Cayley Graphs Generated by Transposition Trees with Missing Edges. Information Sciences, 238, 250-252. [Google Scholar] [CrossRef] 
[10] Cheng, E., Lipták, L. and Steffy, D.E. (2013) Strong Local Diagnosability of (n,k)-Star Graphs and Cayley Graphs Generated by 2-Trees with Missing Edges. Information Processing Letters, 113, 452-456. [Google Scholar] [CrossRef] 
[11] Wang, S.Y. and Ma, X.L. (2018) Diagnosability of Alternating Group Graphs with Missing Edges. Recent Advances in Electrical & Electronic Engineering (Formerly Recent Patents on Electrical & Electronic Engineering), 11, 51-57. [Google Scholar] [CrossRef] 
[12] Wang, S.Y. and Wang, Y.Y. (2019) Diagnosability of Bubble-Sort Star Graphs with Missing Edges. Journal of Interconnection Networks, 19, Article ID: 1950002. [Google Scholar] [CrossRef] 
[13] Feng, W. and Wang, S.Y. (2020) The Diagnosability of Wheel Networks with Missing Edges under the Comparison Model. Mathematics, 8, Article No. 1818. [Google Scholar] [CrossRef] 
[14] 樊畅畅, 王世英, 马晓蕾. 有遗失边的n维超立方立和折叠超立方体在MM*模型下的诊断度[J]. 应用数学进展, 2021, 10(1): 150-159. [Google Scholar] [CrossRef] 
[15] Bondy, J.A. and Murty, U.S.R. (2008) Graph Theory. Springer, New York.
[16] Yuan, J., Liu, A.X., Ma, X., Liu, X.L., Qin, X. and Zhang J.F. (2015) The g-Good-Neighbor Conditional Diagnosability of k-Ary n-Cubes under the PMC Model and MM* Model. IEEE Transactions on Parallel and Distributed Systems, 26, 1165-1177. [Google Scholar] [CrossRef] 
[17] Hungerford, T.W. (1974) Algebra. Springer-Verlag, New York.
[18] Akers, S.B. and Krishanmurthy, B. (1989) A Group-Theoretic Model for Symmetric Interconnection Networks. IEEE Transactions on Computers, 38, 555-566. [Google Scholar] [CrossRef] 
[19] Araki, T. and Kikuchi, Y. (2007) Hamiltonian Laceability of Bubble-Sort Graphs with Edge Faults. Information Sciences, 177, 2679-2691. [Google Scholar] [CrossRef] 
[20] Shi, H.Z., Niu, P.F. and Lu, J.B. (2011) One Conjecture of Bubble-Sort Graphs. Information Processing Letters, 111, 926-929. [Google Scholar] [CrossRef] 
[21] Wang, S.Y. and Wang, Z.H. (2019) The g-Good-Neighbor Diagnosability of Bubble-Sort Graphs under Preparata, Metze, and Chien’s (PMC) Model and Maeng and Malek’s (MM*) Model. Information, 10, Article No. 21. [Google Scholar] [CrossRef] 
[22] Lakshmivarahan, S., Jwo, J.S. and Dhall, S.K. (1993) Symmetry in Interconnection Networks Based on Cayley Graphs of Permutation Groups: A survey, Parallel Computing, 19, 361-407.
https://doi.org10.1016/0167-8191(93)90054-O
[23] Yu, X. and Huang, X.H. (2012) Restricted Vertex Connectivity of Modified Bubble-Sort Graphs. Journal of Xinjiang University (Natural Science Edition), 29, 78-81.
[24] Wang, Y.L. and Wang, S.Y. (2020) The 2-Good-Neighbor Diagnosability of Modified Bubble-Sort Graphs under the PMC and MM* Model. Systems Science & Control Engineering, 8, 258-264. [Google Scholar] [CrossRef] 
[25] Lee, C.W. and Hsieh, S.Y. (2013) Theory and Practice. Wiley-IEEE Computer Society Press, New Jersey, USA.

为你推荐