{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T13:39:35Z","timestamp":1776865175864,"version":"3.51.2"},"reference-count":35,"publisher":"World Scientific Pub Co Pte Lt","issue":"01n02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. Inter. Net."],"published-print":{"date-parts":[[2008,3]]},"abstract":"<jats:p> The diagnosis of faulty processors plays an important role in multiprocessor systems for reliable computing, and the diagnosability of many well-known networks has been explored. Zheng et al. showed that the diagnosability of the n-dimensional star graph S<jats:sub>n<\/jats:sub> is n - 1. Lai et al. introduced a restricted diagnosability of multiprocessor systems called conditional diagnosability. They consider the situation when no faulty set can contain all the neighbors of any vertex in the system. In this paper, we study the conditional diagnosability of Cayley graphs generated by transposition trees (which include the star graphs) under the comparison model, and show that it is 3n - 8 for n \u2265 4, except for the n-dimensional star graph, for which it is 3n - 7. Hence the conditional diagnosability of these graphs is about three times larger than their classical diagnosability. <\/jats:p>","DOI":"10.1142\/s0219265908002175","type":"journal-article","created":{"date-parts":[[2008,9,1]],"date-time":"2008-09-01T01:51:53Z","timestamp":1220233913000},"page":"83-97","source":"Crossref","is-referenced-by-count":96,"title":["CONDITIONAL DIAGNOSABILITY OF CAYLEY GRAPHS GENERATED BY TRANSPOSITION TREES UNDER THE COMPARISON DIAGNOSIS MODEL"],"prefix":"10.1142","volume":"09","author":[{"given":"CHENG-KUAN","family":"LIN","sequence":"first","affiliation":[{"name":"Department of Computer Science, National Chiao Tung University, Hsinchu, Taiwan 30010, R.O.C."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"JIMMY J. M.","family":"TAN","sequence":"additional","affiliation":[{"name":"Department of Computer Science, National Chiao Tung University, Hsinchu, Taiwan 30010, R.O.C."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"LIH-HSING","family":"HSU","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Information Engineering, Providence University, Taichung, Taiwan 43301, R.O.C."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"EDDIE","family":"CHENG","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Statistics, Oakland University, Rochester, MI 48309, U.S.A."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"L\u00c1SZL\u00d3","family":"LIPT\u00c1K","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Statistics, Oakland University, Rochester, MI 48309, U.S.A."}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,21]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1109\/12.21148"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1002\/net.20126"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1109\/12.494105"},{"key":"rf4","volume-title":"Graph Theory with Applications","author":"Bondy J. A.","year":"1980"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1007\/s002240000089"},{"key":"rf8","first-page":"81","volume":"180","author":"Cheng E.","journal-title":"Congressus Numerantium"},{"key":"rf9","first-page":"486","volume":"33","author":"Dahbura A. T.","journal-title":"IEEE Transactions on Computers"},{"key":"rf10","first-page":"1099","volume":"13","author":"Fan J.","journal-title":"IEEE Transactions on Parallel and Distributed Systems"},{"key":"rf11","first-page":"923","volume":"9","author":"Fan J.","journal-title":"IEEE Transactions on Parallel and Distributed Systems"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1995.1006"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1109\/12.485370"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(95)00135-Y"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.01.018"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1002\/1097-0037(200012)36:4<225::AID-NET3>3.0.CO;2-G"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00190-0"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1109\/12.954510"},{"key":"rf19","doi-asserted-by":"publisher","DOI":"10.1142\/S0218126691000215"},{"key":"rf20","first-page":"165","volume":"54","author":"Lai P.-L.","journal-title":"IEEE Transactions on Computers"},{"key":"rf21","first-page":"1064","volume":"53","author":"Lai P.-L.","journal-title":"IEEE Transactions on Computers"},{"key":"rf22","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(93)90060-M"},{"key":"rf23","volume-title":"Introduction to Parallel Algorithms and Architectures: Arrays Trees, Hypercubes","author":"Leighton F. T.","year":"1992"},{"key":"rf24","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2003.09.023"},{"key":"rf25","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.02.007"},{"key":"rf26","first-page":"100","volume":"46","author":"Lin C.-K.","journal-title":"Networks"},{"key":"rf27","doi-asserted-by":"publisher","DOI":"10.1002\/net.20135"},{"key":"rf30","doi-asserted-by":"publisher","DOI":"10.1109\/12.250605"},{"key":"rf31","doi-asserted-by":"publisher","DOI":"10.1109\/12.45203"},{"key":"rf32","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2004.08.004"},{"key":"rf33","first-page":"848","volume":"16","author":"Preparata F. P.","journal-title":"IEEE Transactions on Electronic Computers"},{"key":"rf34","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1996.0028"},{"key":"rf35","doi-asserted-by":"publisher","DOI":"10.1109\/12.2234"},{"key":"rf36","doi-asserted-by":"publisher","DOI":"10.1109\/12.177309"},{"key":"rf37","first-page":"115","volume":"14","author":"Tchuente M.","journal-title":"Ars Combinatoria"},{"key":"rf38","doi-asserted-by":"publisher","DOI":"10.1109\/12.817401"},{"key":"rf39","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2004.09.011"}],"container-title":["Journal of Interconnection Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0219265908002175","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T18:00:46Z","timestamp":1565200846000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0219265908002175"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,3]]},"references-count":35,"journal-issue":{"issue":"01n02","published-online":{"date-parts":[[2011,11,21]]},"published-print":{"date-parts":[[2008,3]]}},"alternative-id":["10.1142\/S0219265908002175"],"URL":"https:\/\/doi.org\/10.1142\/s0219265908002175","relation":{},"ISSN":["0219-2659","1793-6713"],"issn-type":[{"value":"0219-2659","type":"print"},{"value":"1793-6713","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,3]]}}}