{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,30]],"date-time":"2026-06-30T12:09:44Z","timestamp":1782821384363,"version":"3.54.5"},"reference-count":39,"publisher":"Oxford University Press (OUP)","issue":"8","license":[{"start":{"date-parts":[[2021,5,20]],"date-time":"2021-05-20T00:00:00Z","timestamp":1621468800000},"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":["U1905211"],"award-info":[{"award-number":["U1905211"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61972272"],"award-info":[{"award-number":["61972272"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["18KJA520009"],"award-info":[{"award-number":["18KJA520009"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022,8,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Connectivity and diagnosability are two crucial subjects for a network\u2019s ability to tolerate and diagnose faulty processors. The $r$-component connectivity $c\\kappa _{r}(G)$ of a network $G$ is the minimum number of vertices whose deletion results in a graph with at least $r$ components. The $r$-component diagnosability $ct_{r}(G)$ of a network $G$ is the maximum number of faulty vertices that the system can guarantee to identify under the condition that there exist at least $r$ fault-free components. This paper first establishes that the $(r+1)$-component connectivity of $k$-ary $n$-cube $Q^{k}_{n}$ is $c\\kappa _{r+1}(Q^{k}_{n})=-\\frac{1}{2}r^{2}+\\Big(2n-\\frac{1}{2}\\Big)r+1$ for $n\\geq 2$, $k\\geq 4$ and $1\\leq r\\leq n$. In view of $c\\kappa _{r+1}(Q^{k}_{n})$, we prove that the $(r+1)$-component diagnosabilities of $k$-ary $n$-cube $Q^{k}_{n}$ under the PMC model and MM* model are $ct_{r+1}(Q^{k}_{n})=-\\frac{1}{2}r^{2}+\\Big(2n-\\frac{3}{2}\\Big)r+2n$ for $n\\geq 4$, $k\\geq 4$ and $1\\leq r\\leq n-1$.<\/jats:p>","DOI":"10.1093\/comjnl\/bxab054","type":"journal-article","created":{"date-parts":[[2021,5,11]],"date-time":"2021-05-11T11:27:20Z","timestamp":1620732440000},"page":"2197-2208","source":"Crossref","is-referenced-by-count":17,"title":["The Reliability of<i>k<\/i>-Ary<i>n<\/i>-Cube Based on Component Connectivity"],"prefix":"10.1093","volume":"65","author":[{"given":"Mengjie","family":"Lv","sequence":"first","affiliation":[{"name":"School of Computer Science and Technology , Soochow University, Shizi street, Gusu District, Suzhou 215006, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jianxi","family":"Fan","sequence":"additional","affiliation":[{"name":"School of Computer Science and Technology , Soochow University, Shizi street, Gusu District, Suzhou 215006, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jingya","family":"Zhou","sequence":"additional","affiliation":[{"name":"School of Computer Science and Technology , Soochow University, Shizi street, Gusu District, Suzhou 215006, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jia","family":"Yu","sequence":"additional","affiliation":[{"name":"College of Computer Science and Technology , Qingdao University, Ningxia road, Laoshan District, Qingdao 266071, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xiaohua","family":"Jia","sequence":"additional","affiliation":[{"name":"Department of Computer Science , City University of Hong Kong, Tat Chee Avenue Kowloon, Hong Kong 999077, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2021,5,20]]},"reference":[{"key":"2022081612471354000_ref1","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1147\/rd.492.0265","article-title":"Blue gene\/L torus interconnection network","volume":"49","author":"Adiga","year":"2005","journal-title":"IBM J. Res. Develop."},{"key":"2022081612471354000_ref2","first-page":"1","volume-title":"Proc. 1997 ACM\/IEEE Conf. on Supercomputing, Association for Computing Machinery","author":"Anderson","year":"1997"},{"key":"2022081612471354000_ref3","doi-asserted-by":"crossref","first-page":"330","DOI":"10.1109\/SUPERC.1988.44670","volume-title":"Proceedings Supercomputing","author":"Borkar","year":"1988"},{"key":"2022081612471354000_ref4","doi-asserted-by":"crossref","first-page":"1021","DOI":"10.1109\/12.403718","article-title":"Lee distance and topological properties of k-ary n-cubes","volume":"44","author":"Bose","year":"1995","journal-title":"IEEE Trans. Comput."},{"key":"2022081612471354000_ref5","first-page":"1","article-title":"Generalized connectivity in graphs","volume":"2","author":"Chartrand","year":"1984","journal-title":"Bull. Bombay Math. Colloq."},{"key":"2022081612471354000_ref6","doi-asserted-by":"crossref","first-page":"108","DOI":"10.1016\/j.tcs.2020.06.015","article-title":"The component (edge) connectivity of shuffle-cubes","volume":"835","author":"Ding","year":"2020","journal-title":"Theor. Comput. Sci."},{"key":"2022081612471354000_ref7","doi-asserted-by":"crossref","first-page":"372","DOI":"10.1007\/s11390-019-1893-0","article-title":"Optimally embedding 3-ary n-cubes into grids","volume":"34","author":"Fan","year":"2019","journal-title":"J. Comput. Syst. Technol."},{"key":"2022081612471354000_ref8","first-page":"179101:1","article-title":"Communication and performance evaluation of 3-ary n-cubes onto network-on-chips","volume":"65","author":"Fan","year":"2021","journal-title":"Sci. China (Inf. Sci.)"},{"key":"2022081612471354000_ref9","doi-asserted-by":"crossref","first-page":"298","DOI":"10.21136\/CMJ.1973.101168","article-title":"Algebraic connectivity of graphs","volume":"23","author":"Fiedler","year":"1973","journal-title":"Czechoslov. Math. J."},{"key":"2022081612471354000_ref10","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1142\/S0129054120500100","article-title":"On component connectivity of hierarchical star networks","volume":"31","author":"Gu","year":"2020","journal-title":"Int. J. Found. Comput. Sci."},{"key":"2022081612471354000_ref11","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1016\/j.tcs.2017.05.036","article-title":"Equal relation between the extra connectivity and pessimistic diagnosability for some regular graphs","volume":"690","author":"Gu","year":"2017","journal-title":"Theoret. Comput. Sci."},{"key":"2022081612471354000_ref12","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1016\/j.tcs.2016.02.024","article-title":"Relationship between conditional diagnosability and 2-extra connectivity of symmetric graphs","volume":"627","author":"Hao","year":"2016","journal-title":"Theoret. Comput. Sci."},{"key":"2022081612471354000_ref13","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1080\/00207160.2011.638978","article-title":"Component connectivity of the hypercubes","volume":"89","author":"Hsu","year":"2012","journal-title":"Int. J. Comput. Math."},{"key":"2022081612471354000_ref14","doi-asserted-by":"crossref","first-page":"839","DOI":"10.1109\/TC.2012.18","article-title":"The conditional diagnosability of k-ary n-cubes under the comparison diagnosis model","volume":"62","author":"Hsieh","year":"2013","journal-title":"IEEE Trans. Comput."},{"key":"2022081612471354000_ref15","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1093\/comjnl\/bxz136","article-title":"Relationship between extra connectivity and component connectivity in networks","volume":"64","author":"Li","year":"2021","journal-title":"Comput. J."},{"key":"2022081612471354000_ref16","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.jcss.2017.11.004","article-title":"The relationship between extra connectivity and conditional diagnosability of regular graphs under the PMC model","volume":"95","author":"Lin","year":"2018","journal-title":"J. Comput. Syst. Sci."},{"key":"2022081612471354000_ref17","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1109\/TR.2017.2760905","article-title":"The relationship between g-restricted connectivity and g-good-neighbor fault-diagnosability of general regular networks","volume":"67","author":"Lin","year":"2018","journal-title":"IEEE Trans. Rel."},{"key":"2022081612471354000_ref18","doi-asserted-by":"crossref","first-page":"1086","DOI":"10.1109\/TDSC.2017.2726541","article-title":"Relating extra connectivity and extra conditional diagnosability in regular networks","volume":"16","author":"Lin","year":"2019","journal-title":"IEEE Trans. Dependable Secure Comput."},{"key":"2022081612471354000_ref19","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1016\/j.tcs.2019.03.030","article-title":"The h-extra connectivity of k-ary n-cubes","volume":"784","author":"Liu","year":"2019","journal-title":"Theor. Comput. Sci."},{"key":"2022081612471354000_ref20","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxaa078","article-title":"The conditional reliability evaluation of data center network BCDC","author":"Lv","year":"2020","journal-title":"Comput. J."},{"key":"2022081612471354000_ref21","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1016\/j.tcs.2019.12.001","article-title":"The extra connectivity and extra diagnosability of regular interconnection networks","volume":"809","author":"Lv","year":"2020","journal-title":"Theor. Comput. Sci."},{"key":"2022081612471354000_ref22","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.tcs.2020.05.003","article-title":"The reliability analysis of k-ary n-cube networks","volume":"835","author":"Lv","year":"2020","journal-title":"Theor. Comput. Sci."},{"key":"2022081612471354000_ref23","first-page":"173","volume-title":"Proc. of the 11th Int. Fault-Tolerant Computing 1981","author":"Maeng","year":"1981"},{"key":"2022081612471354000_ref24","doi-asserted-by":"crossref","first-page":"848","DOI":"10.1109\/PGEC.1967.264748","article-title":"On the connection assignment problem of diagnosable systems","volume":"EC-16","author":"Preparata","year":"1967","journal-title":"IEEE Trans. Electron. Comput."},{"key":"2022081612471354000_ref25","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":"2022081612471354000_ref26","doi-asserted-by":"crossref","first-page":"1071","DOI":"10.1109\/TPDS.2007.70787","article-title":"Embedding long paths in k-ary n-cubes with faulty nodes and links","volume":"19","author":"Stewart","year":"2008","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"2022081612471354000_ref27","doi-asserted-by":"crossref","first-page":"1839","DOI":"10.1093\/comjnl\/bxw037","article-title":"The 2-extra connectivity and 2-extra diagnosability of bubble-sort star graph networks","volume":"59","author":"Wang","year":"2016","journal-title":"Comput. J."},{"key":"2022081612471354000_ref28","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1016\/j.amc.2017.02.006","article-title":"The 2-good-neighbor (2-extra) diagnosability of alternating group graph networks under the PMC model and MM* model","volume":"305","author":"Wang","year":"2017","journal-title":"Appl. Math Comput."},{"key":"2022081612471354000_ref29","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1016\/j.ins.2014.01.044","article-title":"Hamiltonian path embeddings in conditional faulty k-ary n-cubes","volume":"268","author":"Wang","year":"2014","journal-title":"Inform. Sci."},{"key":"2022081612471354000_ref30","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1016\/j.tcs.2017.02.010","article-title":"Conditional diagnosability of a class of matching composition networks under the comparison model","volume":"674","author":"Xu","year":"2017","journal-title":"Theor. Comput. Sci."},{"key":"2022081612471354000_ref31","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/j.tcs.2016.11.007","article-title":"The g-good-neighbor diagnosability of (n, k)-star graphs","volume":"659","author":"Xu","year":"2017","journal-title":"Theor. Comput. Sci."},{"key":"2022081612471354000_ref32","first-page":"625","article-title":"Reliability of complete cubic networks under the condition of g-good-neighbor","volume":"60","author":"Xu","year":"2017","journal-title":"Comput. J."},{"key":"2022081612471354000_ref33","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1016\/j.ipl.2005.10.003","article-title":"Minimum neighborhood in a generalized cube","volume":"97","author":"Yang","year":"2006","journal-title":"Inf. Process. Lett."},{"key":"2022081612471354000_ref34","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1016\/j.ins.2014.03.119","article-title":"Conditional connectivity of recursive interconnection networks respect to embedding restriction","volume":"279","author":"Yang","year":"2014","journal-title":"Inform. Sci."},{"key":"2022081612471354000_ref35","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxaa155","article-title":"The component diagnosability of hypercubes with large-scale faulty nodes","author":"Zhang","year":"2020","journal-title":"Comput. J."},{"key":"2022081612471354000_ref36","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1016\/j.tcs.2016.05.035","article-title":"Component connectivity of hypercubes","volume":"640","author":"Zhao","year":"2016","journal-title":"Theor. Comput. Sci."},{"key":"2022081612471354000_ref37","doi-asserted-by":"crossref","first-page":"388","DOI":"10.1016\/j.dam.2018.09.022","article-title":"Conditional connectivity of folded hypercubes","volume":"257","author":"Zhao","year":"2019","journal-title":"Discrete Appl. Math."},{"key":"2022081612471354000_ref38","doi-asserted-by":"crossref","first-page":"547","DOI":"10.1109\/TC.2013.228","article-title":"The t\/k-diagnosability of star graph networks","volume":"64","author":"Zhou","year":"2015","journal-title":"IEEE Trans. Comput."},{"key":"2022081612471354000_ref39","doi-asserted-by":"crossref","first-page":"1847","DOI":"10.1109\/TC.2013.64","article-title":"Relating diagnosability, strong diagnosability and conditional diagnosability of strong networks","volume":"63","author":"Zhu","year":"2014","journal-title":"IEEE Trans. Comput."}],"container-title":["The Computer Journal"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/comjnl\/article-pdf\/65\/8\/2197\/45329703\/bxab054.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/comjnl\/article-pdf\/65\/8\/2197\/45329703\/bxab054.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,3]],"date-time":"2023-11-03T15:38:28Z","timestamp":1699025908000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comjnl\/article\/65\/8\/2197\/6279277"}},"subtitle":[],"editor":[{"given":"Iain","family":"Stewart","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"editor"}]}],"short-title":[],"issued":{"date-parts":[[2021,5,20]]},"references-count":39,"journal-issue":{"issue":"8","published-online":{"date-parts":[[2021,5,20]]},"published-print":{"date-parts":[[2022,8,11]]}},"URL":"https:\/\/doi.org\/10.1093\/comjnl\/bxab054","relation":{},"ISSN":["0010-4620","1460-2067"],"issn-type":[{"value":"0010-4620","type":"print"},{"value":"1460-2067","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2022,8]]},"published":{"date-parts":[[2021,5,20]]}}}