{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,19]],"date-time":"2025-11-19T06:59:53Z","timestamp":1763535593792,"version":"build-2065373602"},"reference-count":27,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2019,1,10]],"date-time":"2019-01-10T00:00:00Z","timestamp":1547078400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61772010"],"award-info":[{"award-number":["61772010"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Information"],"abstract":"<jats:p>Diagnosability of a multiprocessor system is an important topic of study. A measure for fault diagnosis of the system restrains that every fault-free node has at least g fault-free neighbor vertices, which is called the g-good-neighbor diagnosability of the system. As a famous topology structure of interconnection networks, the n-dimensional bubble-sort graph     B n     has many good properties. In this paper, we prove that (1) the 1-good-neighbor diagnosability of     B n     is     2 n \u2212 3     under Preparata, Metze, and Chien\u2019s (PMC) model for     n \u2265 4     and Maeng and Malek\u2019s (MM)     \u2217     model for     n \u2265 5    ; (2) the 2-good-neighbor diagnosability of     B n     is     4 n \u2212 9     under the PMC model and the MM     \u2217     model for     n \u2265 4    ; (3) the 3-good-neighbor diagnosability of     B n     is     8 n \u2212 25     under the PMC model and the MM     \u2217     model for     n \u2265 7    .<\/jats:p>","DOI":"10.3390\/info10010021","type":"journal-article","created":{"date-parts":[[2019,1,11]],"date-time":"2019-01-11T04:10:16Z","timestamp":1547179816000},"page":"21","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["The g-Good-Neighbor Diagnosability of Bubble-Sort Graphs under Preparata, Metze, and Chien\u2019s (PMC) Model and Maeng and Malek\u2019s (MM)* Model"],"prefix":"10.3390","volume":"10","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9335-3005","authenticated-orcid":false,"given":"Shiying","family":"Wang","sequence":"first","affiliation":[{"name":"College of Mathematics and Information Science, Henan Normal University, Xinxiang 453007, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhenhua","family":"Wang","sequence":"additional","affiliation":[{"name":"College of Mathematics and Information Science, Henan Normal University, Xinxiang 453007, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2019,1,10]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"848","DOI":"10.1109\/PGEC.1967.264748","article-title":"On the connection assignment problem of diagnosable systems","volume":"16","author":"Preparata","year":"1967","journal-title":"IEEE Trans. Comput."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"585","DOI":"10.1109\/TC.1976.1674658","article-title":"A Theory of Diagnosability of Digital Systems","volume":"25","author":"Barsi","year":"1976","journal-title":"IEEE Trans. Comput."},{"key":"ref_3","unstructured":"Maeng, J., and Malek, M. (1981, January 24\u201326). A comparison connection assignment for self-diagnosis of multiprocessor systems. Proceedings of the 11th International Symposium on Fault-Tolerant Computing, Portland, OR, USA."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"486","DOI":"10.1109\/TC.1984.1676472","article-title":"An O(n2.5) Fault identification algorithm for diagnosable systems","volume":"33","author":"Dahbura","year":"1984","journal-title":"IEEE Trans. Comput."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"10406","DOI":"10.1016\/j.amc.2012.03.092","article-title":"The g-good-neighbor conditional diagnosability of hypercube under PMC model","volume":"218","author":"Peng","year":"2012","journal-title":"Appl. Math. Comput."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"3002","DOI":"10.1109\/TPDS.2013.290","article-title":"Structural properties and conditional diagnosability of star graphs by using the PMC Model","volume":"25","author":"Chang","year":"2014","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"1005","DOI":"10.1142\/S0129054107005108","article-title":"Fault resiliency of Cayley graphs generated by transpositions","volume":"18","author":"Cheng","year":"2007","journal-title":"Int. J. Found. Comput. Sci."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"1099","DOI":"10.1109\/TPDS.2002.1041887","article-title":"Diagnosability of crossed cubes under the comparison diagnosis model","volume":"13","author":"Fan","year":"2002","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"ref_9","unstructured":"Hu, S.-C., and Yang, C.-B. (1995, January 15\u201317). Fault tolerance on star graphs. Proceedings of the First Aizu International Symposium on Parallel Algorithms\/Architecture Synthesis, Aizu-Wakamatsu, Japan."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1109\/TC.2005.19","article-title":"Conditional diagnosability measures for large multiprocessor systems","volume":"54","author":"Lai","year":"2005","journal-title":"IEEE Trans. Comput."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1142\/S0219265908002175","article-title":"Conditional diagnosability of Cayley graphs generated by transposition trees under the comparison diagnosis Model","volume":"9","author":"Lin","year":"2008","journal-title":"J. Interconnect. Netw."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Ren, Y., and Wang, S. (2015, January 12\u201314). Diagnosability of bubble-sort graph networks under the comparison diagnosis model. Proceedings of the 2015 International Conference on Computational Intelligence and Communication Networks, Jabalpur, India.","DOI":"10.1109\/CICN.2015.321"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"620","DOI":"10.1080\/00207160.2015.1119817","article-title":"The 1-good-neighbor diagnosability of Cayley graphs generated by transposition trees under the PMC model and MM* model","volume":"94","author":"Wang","year":"2017","journal-title":"Int. J. Comput. Math."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"108","DOI":"10.1016\/j.dam.2017.02.023","article-title":"The 1-good-neighbor connectivity and diagnosability of Cayley graphs generated by complete graphs","volume":"246","author":"Wang","year":"2018","journal-title":"Discret. Appl. Math."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1051\/ita\/2017008","article-title":"The connectivity and nature diagnosability of expanded k-ary n-cubes","volume":"51","author":"Wang","year":"2017","journal-title":"RAIRO-Theor. Inform. Appl."},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Wang, S., and Ren, Y. (2018). g-Good-neighbor diagnosability of arrangement graphs under the PMC model and MM* model. Information, 9.","DOI":"10.3390\/info9110275"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"1850005","DOI":"10.1142\/S0219265918500056","article-title":"A note on the nature diagnosability of alternating group graphs under the PMC model and MM* model","volume":"18","author":"Wang","year":"2018","journal-title":"J. Interconnect. Netw."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Wang, S., and Wang, M. (2018). The g-good-neighbor and g-extra diagnosability of networks. Theor. Comput. Sci., in press.","DOI":"10.1016\/j.tcs.2018.09.002"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"574","DOI":"10.1016\/j.ipl.2016.04.005","article-title":"The g-good-neighbor conditional diagnosability of n-dimensional hypercubes under the MM* model","volume":"116","author":"Wang","year":"2016","journal-title":"Inf. Process. Lett."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"1165","DOI":"10.1109\/TPDS.2014.2318305","article-title":"The g-good-neighbor conditional diagnosability of k-ary n-cubes under the PMC model and MM* model","volume":"26","author":"Yuan","year":"2015","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1016\/j.ipl.2004.09.011","article-title":"Diagnosability of star graphs under the comparison diagnosis Model","volume":"93","author":"Zheng","year":"2005","journal-title":"Inf. Process. Lett."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Bondy, J.A., and Murty, U.S.R. (2007). Graph Theory, Springer.","DOI":"10.1007\/978-3-7643-7400-6"},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Hungerford, T.W. (1974). Algebra, Springer.","DOI":"10.1007\/978-1-4612-6101-8_4"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"555","DOI":"10.1109\/12.21148","article-title":"Balakrishnan Krishnamurthy, A group-theoretic model for symmetric interconnection networks","volume":"38","author":"Akers","year":"1989","journal-title":"IEEE Trans. Comput."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"2662","DOI":"10.1016\/j.camwa.2007.10.016","article-title":"Orienting Cayley graphs generated by transposition trees","volume":"55","author":"Cheng","year":"2008","journal-title":"Comput. Math. Appl."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"1027","DOI":"10.1016\/j.ipl.2010.09.001","article-title":"Conditional connectivity of Cayley graphs generated by transposition trees","volume":"110","author":"Yang","year":"2010","journal-title":"Inf. Process. Lett."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"933","DOI":"10.1007\/s10255-017-0708-8","article-title":"Conditional connectivity of bubble sort graphs","volume":"33","author":"Shi","year":"2017","journal-title":"Acta Math. Appl. Sin."}],"container-title":["Information"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2078-2489\/10\/1\/21\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T12:24:54Z","timestamp":1760185494000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2078-2489\/10\/1\/21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,1,10]]},"references-count":27,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2019,1]]}},"alternative-id":["info10010021"],"URL":"https:\/\/doi.org\/10.3390\/info10010021","relation":{},"ISSN":["2078-2489"],"issn-type":[{"type":"electronic","value":"2078-2489"}],"subject":[],"published":{"date-parts":[[2019,1,10]]}}}