{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,20]],"date-time":"2025-11-20T12:44:41Z","timestamp":1763642681226,"version":"3.37.3"},"reference-count":22,"publisher":"Oxford University Press (OUP)","issue":"9","license":[{"start":{"date-parts":[[2019,11,14]],"date-time":"2019-11-14T00:00:00Z","timestamp":1573689600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"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"}]},{"DOI":"10.13039\/100009555","name":"Henan Normal University","doi-asserted-by":"publisher","award":["Xiao 20180529","20180454"],"award-info":[{"award-number":["Xiao 20180529","20180454"]}],"id":[{"id":"10.13039\/100009555","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020,8,20]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Diagnosability of a multiprocessor system is an important research topic. The system and an interconnection network have an underlying topology, which is usually presented by a graph. Under the Maeng and Malek's (MM) model, to diagnose the system, a node sends the same task to two of its neighbors, and then compares their responses. The MM$^{*}$ is a special case of the MM model and each node must test all pairs of its adjacent nodes. In 2009, Chiang and Tan (Using node diagnosability to determine $t$-diagnosability under the comparison diagnosis (cd) model. IEEE Trans. Comput., 58, 251\u2013259) proposed a new viewpoint for fault diagnosis of the system, namely, the node diagnosability. As a new topology structure of interconnection networks, the nest graph $CK_{n}$ has many good properties. In this paper, we study the local diagnosability of $CK_{n}$ and show it has the strong local diagnosability property even if there exist $(\\frac{n(n-1)}{2}-2)$ missing edges in it under the MM$^{*}$ model, and the result is optimal with respect to the number of missing edges.<\/jats:p>","DOI":"10.1093\/comjnl\/bxz096","type":"journal-article","created":{"date-parts":[[2019,8,3]],"date-time":"2019-08-03T11:11:36Z","timestamp":1564830696000},"page":"1438-1447","source":"Crossref","is-referenced-by-count":1,"title":["Diagnosability of the Cayley Graph Generated by Complete Graph with Missing Edges under the MM$^{\\ast }$ Model"],"prefix":"10.1093","volume":"63","author":[{"given":"Yunxia","family":"Ren","sequence":"first","affiliation":[{"name":"Henan Engineering Laboratory for Big Data Statistical Analysis and Optimal Control, School of Mathematics and Information Science, Henan Normal University, Xinxiang, Henan 453007, PR China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shiying","family":"Wang","sequence":"additional","affiliation":[{"name":"Henan Engineering Laboratory for Big Data Statistical Analysis and Optimal Control, School of Mathematics and Information Science, Henan Normal University, Xinxiang, Henan 453007, PR China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2019,11,14]]},"reference":[{"key":"2020091506440829000_ref1","doi-asserted-by":"crossref","first-page":"486","DOI":"10.1109\/TC.1984.1676472","article-title":"An $O\\left ({n}^{2.5}\\right )$ fault identification algorithm for diagnosable systems","volume":"33","author":"Dahbura","year":"1984","journal-title":"IEEE Trans. Comput."},{"key":"2020091506440829000_ref2","first-page":"173\u2013175","article-title":"A comparison connection assignment for self-diagnosis of multiprocessor systems","volume-title":"Proc.11th Int. Symposium on Fault-Tolerant Computing","author":"Maeng","year":"1981"},{"key":"2020091506440829000_ref3","doi-asserted-by":"crossref","first-page":"1386","DOI":"10.1109\/12.177309","article-title":"On self-diagnosable multiprocessor systems: diagnosis by the comparison approach","volume":"41","author":"Sengupta","year":"1992","journal-title":"IEEE Trans. Comput."},{"key":"2020091506440829000_ref4","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1109\/TC.2008.158","article-title":"Using node diagnosability to determine $t$-diagnosability under the comparison diagnosis model.","volume":"58","author":"Chiang","year":"2009","journal-title":"IEEE Trans. Comput."},{"key":"2020091506440829000_ref5","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1016\/j.ins.2011.11.012","article-title":"Diagnosability of star graph with missing edges","volume":"188","author":"Chiang","year":"2012","journal-title":"Inf. Sci."},{"year":"2013","author":"Cheng","key":"2020091506440829000_ref6"},{"key":"2020091506440829000_ref7","doi-asserted-by":"crossref","first-page":"452","DOI":"10.1016\/j.ipl.2013.03.002","article-title":"Strong local diagnosability of $\\left (n,k\\right )$-star graphs and Cayley graphs generated by 2-trees with missing edges","volume":"113","author":"Cheng","year":"2013","journal-title":"Inf. Process. Lett."},{"key":"2020091506440829000_ref8","first-page":"51","article-title":"Diagnosability of Alternating Group Graphs with Missing Edges","volume":"11","author":"Wang","year":"2018","journal-title":"Recent Adv. Electrical Electronic Eng."},{"key":"2020091506440829000_ref9","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."},{"volume-title":"Graph Theory","year":"1976","author":"Bondy","key":"2020091506440829000_ref10"},{"volume-title":"Algebra","year":"1974","author":"Hungerford","key":"2020091506440829000_ref11"},{"key":"2020091506440829000_ref12","doi-asserted-by":"crossref","first-page":"555","DOI":"10.1109\/12.21148","article-title":"A group-theoretic model for symmetric interconnection networks","volume":"38","author":"Akers","year":"1989","journal-title":"IEEE Trans. Comput."},{"key":"2020091506440829000_ref13","doi-asserted-by":"crossref","first-page":"4877","DOI":"10.1016\/j.ins.2007.05.034","article-title":"Linearly many faults in Cayley graphs generated by transposition trees","volume":"177","author":"Cheng","year":"2007","journal-title":"Inf. Sci."},{"key":"2020091506440829000_ref14","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":"2020091506440829000_ref15","doi-asserted-by":"crossref","first-page":"178","DOI":"10.1016\/j.dam.2014.10.019","article-title":"Diameters of Cayley graphs generated by transposition trees","volume":"184","author":"Kraft","year":"2015","journal-title":"Discrete Appl. Math."},{"key":"2020091506440829000_ref16","doi-asserted-by":"crossref","first-page":"3087","DOI":"10.1016\/j.disc.2012.06.007","article-title":"Fault-tolerant Hamiltonian laceability of Cayley graphs generated by transposition trees","volume":"312","author":"Li","year":"2012","journal-title":"Discrete Math."},{"key":"2020091506440829000_ref17","doi-asserted-by":"crossref","first-page":"748","DOI":"10.1016\/j.disc.2009.09.002","article-title":"Bipancyclic properties of Cayley graphs generated by transpositions","volume":"310","author":"Tanaka","year":"2010","journal-title":"Discrete Math."},{"key":"2020091506440829000_ref18","doi-asserted-by":"crossref","first-page":"264","DOI":"10.1016\/j.aml.2008.03.021","article-title":"A kind of conditional vertex connectivity of star graphs","volume":"22","author":"Wan","year":"2009","journal-title":"Appl. Math. Lett."},{"key":"2020091506440829000_ref19","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":"2020091506440829000_ref20","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":"Discrete Appl. Math."},{"key":"2020091506440829000_ref21","doi-asserted-by":"crossref","first-page":"144","DOI":"10.1093\/computer_journal\/bxy054","article-title":"The generalized three-connectivity of two kinds of Cayley graphs","volume":"62","author":"Zhao","year":"2019","journal-title":"Computer J."},{"key":"2020091506440829000_ref22","doi-asserted-by":"crossref","first-page":"536","DOI":"10.1016\/j.ins.2014.10.032","article-title":"Some conditional vertex connectivities of complete transposition graphs","volume":"295","author":"Wang","year":"2015","journal-title":"Inf. Sci."}],"container-title":["The Computer Journal"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/comjnl\/article-pdf\/63\/9\/1438\/33747663\/bxz096.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"http:\/\/academic.oup.com\/comjnl\/article-pdf\/63\/9\/1438\/33747663\/bxz096.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,9,15]],"date-time":"2020-09-15T10:44:29Z","timestamp":1600166669000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comjnl\/article\/63\/9\/1438\/5612728"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,11,14]]},"references-count":22,"journal-issue":{"issue":"9","published-online":{"date-parts":[[2019,11,14]]},"published-print":{"date-parts":[[2020,8,20]]}},"URL":"https:\/\/doi.org\/10.1093\/comjnl\/bxz096","relation":{},"ISSN":["0010-4620","1460-2067"],"issn-type":[{"type":"print","value":"0010-4620"},{"type":"electronic","value":"1460-2067"}],"subject":[],"published-other":{"date-parts":[[2020,9]]},"published":{"date-parts":[[2019,11,14]]}}}