{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,13]],"date-time":"2026-05-13T03:54:15Z","timestamp":1778644455838,"version":"3.51.4"},"reference-count":47,"publisher":"Oxford University Press (OUP)","issue":"1","license":[{"start":{"date-parts":[[2020,2,15]],"date-time":"2020-02-15T00:00:00Z","timestamp":1581724800000},"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":["61572337"],"award-info":[{"award-number":["61572337"]}],"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":["61602333"],"award-info":[{"award-number":["61602333"]}],"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":["61872257"],"award-info":[{"award-number":["61872257"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Natural Science Foundation of the Jiangsu Higher Education Institutions of China","award":["18KJA520009"],"award-info":[{"award-number":["18KJA520009"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021,1,19]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Connectivity is a classic measure for reliability of a multiprocessor system in the case of processor failures. Extra connectivity and component connectivity are two important indicators of the reliability of a multiprocessor system in presence of failing processors. The $h$-extra connectivity $\\kappa _{h}(G)$ of a graph $G$ is the minimum number of nodes whose removal will disconnect $G$, and every remaining component has at least $h+1$ nodes. Moreover, the $h$-component connectivity $c\\kappa _{h}(G)$ of $G$ is the minimum number of nodes whose deletion results in a graph with at least $h$ components. However, the extra connectivity and component connectivity of many well-known networks have been independently investigated. In this paper, we determine the relationship between extra connectivity and component connectivity of general networks. As applications, the extra connectivity and component connectivity are explored for some well-known networks, including complete cubic networks, hierarchical cubic networks, generalized exchanged hypercubes, dual-cube-like networks, Cayley graphs generated by transposition trees and hierarchical hypercubes as well.<\/jats:p>","DOI":"10.1093\/comjnl\/bxz136","type":"journal-article","created":{"date-parts":[[2020,2,10]],"date-time":"2020-02-10T20:09:43Z","timestamp":1581365383000},"page":"38-53","source":"Crossref","is-referenced-by-count":54,"title":["Relationship Between Extra Connectivity And Component Connectivity In Networks"],"prefix":"10.1093","volume":"64","author":[{"given":"Xiaoyan","family":"Li","sequence":"first","affiliation":[{"name":"School of Computer Science and Technology, Soochow University, 1 Shizi Street, Suzhou 215006, China"},{"name":"College of Mathematics and Computer Science, Fuzhou University, 2 Xueyuan Road, Fuzhou 350108, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Cheng-Kuan","family":"Lin","sequence":"additional","affiliation":[{"name":"College of Mathematics and Computer Science, Fuzhou University, 2 Xueyuan Road, Fuzhou 350108, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jianxi","family":"Fan","sequence":"additional","affiliation":[{"name":"School of Computer Science and Technology, Soochow University, 1 Shizi Street, Suzhou 215006, China"},{"name":"Jiangsu High Technology Research Key Laboratory for Wireless Sensor Networks, 66 Xinmofan Road, Nanjing 210003, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiaohua","family":"Jia","sequence":"additional","affiliation":[{"name":"Department of Computer Science, City University of Hong Kong, 83 Tat Chee Avenue, Kowloon, Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Baolei","family":"Cheng","sequence":"additional","affiliation":[{"name":"School of Computer Science and Technology, Soochow University, 1 Shizi Street, Suzhou 215006, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jingya","family":"Zhou","sequence":"additional","affiliation":[{"name":"School of Computer Science and Technology, Soochow University, 1 Shizi Street, Suzhou 215006, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2020,2,15]]},"reference":[{"key":"2021011807350543000_ref1","doi-asserted-by":"crossref","first-page":"1060","DOI":"10.1109\/TC.2013.31","article-title":"On the optimal allocation of virtual resources in cloud computing networks","volume":"62","author":"Papagianni","year":"2013","journal-title":"IEEE Trans. Comput."},{"key":"2021011807350543000_ref2","doi-asserted-by":"crossref","first-page":"34","DOI":"10.1016\/j.ins.2016.05.048","article-title":"Trustworthiness-hypercube-based reliable communication in mobile social networks","volume":"369","author":"Lin","year":"2016","journal-title":"Inform. Sci."},{"key":"2021011807350543000_ref3","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1093\/comjnl\/bxx057","article-title":"Diagnosability evaluation of the data center network DCell","volume":"61","author":"Li","year":"2018","journal-title":"Comput. J."},{"key":"2021011807350543000_ref4","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1016\/j.future.2017.04.011","article-title":"An insertion-deletion-compensation model with Poisson process for scale-free networks","volume":"83","author":"Li","year":"2018","journal-title":"Future Gener. Comput. Sys."},{"key":"2021011807350543000_ref5","first-page":"333","article-title":"A predictive scheduling framework for fast and distributed stream data processing","volume-title":"Proc. BigData\u201915","author":"Li","year":"2015"},{"key":"2021011807350543000_ref6","doi-asserted-by":"crossref","first-page":"2767","DOI":"10.1109\/TC.2015.2493548","article-title":"Multicast-based testing and thermal-aware test scheduling for 3D ICs with a stacked network-on-chip","volume":"65","author":"Xiang","year":"2016","journal-title":"IEEE Trans. Comput."},{"key":"2021011807350543000_ref7","first-page":"346","article-title":"Conditional connectivity","volume":"143","author":"Harary","year":"1983","journal-title":"Networks"},{"key":"2021011807350543000_ref8","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/0020-0190(88)90025-7","article-title":"On computing a conditional edge-connectivity of a graph","volume":"27","author":"Esfahanian","year":"1988","journal-title":"Inform. Process. Lett."},{"key":"2021011807350543000_ref9","doi-asserted-by":"crossref","first-page":"240","DOI":"10.1109\/TR.1986.4335424","article-title":"Synthesis of reliable networks\u2014a survey","volume":"35","author":"Boesch","year":"1986","journal-title":"IEEE Trans. Rel."},{"key":"2021011807350543000_ref10","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1016\/j.tcs.2015.11.050","article-title":"{2,3}-Restricted connectivity of locally twisted cubes","volume":"615","author":"Hsieh","year":"2016","journal-title":"Theor. Comput. Sci."},{"key":"2021011807350543000_ref11","doi-asserted-by":"crossref","first-page":"1586","DOI":"10.1109\/12.42131","article-title":"Generalized measures of fault tolerance with application to $\\mathrm{n}$-cube networks","volume":"38","author":"Esfahanian","year":"1989","journal-title":"IEEE Trans. Comput."},{"key":"2021011807350543000_ref12","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/0012-365X(94)00369-T","article-title":"On the extraconnectivity of graphs","volume":"155","author":"F\u00e0brega","year":"1996","journal-title":"Discrete Math."},{"key":"2021011807350543000_ref13","first-page":"8489","article-title":"Superconnectivity of $k$-regular interconnection networks","volume":"217","author":"Chen","year":"2011","journal-title":"Appl. Math. Comput."},{"key":"2021011807350543000_ref14","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":"2021011807350543000_ref15","first-page":"1213","article-title":"Connectivity results of hierarchical cubic networks as associated with linearly many faults","volume-title":"Proc. CSE\u201914","author":"Cheng","year":"2014"},{"key":"2021011807350543000_ref16","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":"2021011807350543000_ref17","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":"2021011807350543000_ref18","volume-title":"Graph Theory with Applications","author":"Bondy","year":"2008"},{"key":"2021011807350543000_ref19","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1109\/71.372797","article-title":"Hierarchical cubic networks","volume":"6","author":"Ghose","year":"1995","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"2021011807350543000_ref20","doi-asserted-by":"crossref","first-page":"1440","DOI":"10.1093\/comjnl\/bxr137","article-title":"Node-to-set disjoint-path routing in hierarchical cubic networks","volume":"55","author":"Bossard","year":"2012","journal-title":"Comput. J."},{"key":"2021011807350543000_ref21","doi-asserted-by":"crossref","first-page":"1550007","DOI":"10.1142\/S0219265915500073","article-title":"Connectivity results of complete cubic networks as associated with linearly many faults","volume":"15","author":"Cheng","year":"2015","journal-title":"J. Interconnect. Netw."},{"key":"2021011807350543000_ref22","doi-asserted-by":"crossref","first-page":"421","DOI":"10.1016\/j.tcs.2015.10.030","article-title":"On the conditional fault tolerance and diagnosability of hierarchical cubic networks","volume":"609","author":"Zhou","year":"2016","journal-title":"Theoret. Comput. Sci."},{"key":"2021011807350543000_ref23","first-page":"1165","article-title":"The reliability of complete cubic networks under the condition of $g$-good-neighbor","volume":"26","author":"Xu","year":"2016","journal-title":"Comput. J."},{"key":"2021011807350543000_ref24","doi-asserted-by":"crossref","first-page":"866","DOI":"10.1109\/TPDS.2005.113","article-title":"The exchanged hypercube","volume":"16","author":"Loh","year":"2005","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"2021011807350543000_ref25","doi-asserted-by":"crossref","first-page":"533","DOI":"10.1016\/j.ipl.2013.04.007","article-title":"Generalized measures of fault tolerance in exchanged hypercubes","volume":"113","author":"Li","year":"2013","journal-title":"Inform. Process. Lett."},{"key":"2021011807350543000_ref26","doi-asserted-by":"crossref","first-page":"529","DOI":"10.1016\/j.dam.2015.11.014","article-title":"A strong connectivity property of the generalized exchanged hypercube","volume":"216","author":"Cheng","year":"2017","journal-title":"Discrete Appl. Math."},{"key":"2021011807350543000_ref27","doi-asserted-by":"crossref","first-page":"144","DOI":"10.1016\/j.dam.2015.09.002","article-title":"The restricted $h$-connectivity of the data center network DCell","volume":"203","author":"Wang","year":"2016","journal-title":"Discrete Appl. Math."},{"key":"2021011807350543000_ref28","doi-asserted-by":"crossref","first-page":"176","DOI":"10.1109\/TC.2005.33","article-title":"The $t\/k$-diagnosability of the BC graphs","volume":"54","author":"Fan","year":"2005","journal-title":"IEEE Trans. Comput."},{"key":"2021011807350543000_ref29","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1007\/s11227-007-0167-8","article-title":"On conditional diagnosability and reliability of the BC networks","volume":"45","author":"Zhu","year":"2008","journal-title":"J. Supercomput."},{"key":"2021011807350543000_ref30","doi-asserted-by":"crossref","first-page":"887","DOI":"10.1016\/j.aml.2008.07.016","article-title":"Extraconnectivity of hypercubes","volume":"22","author":"Yang","year":"2009","journal-title":"Appl. Math. Lett."},{"key":"2021011807350543000_ref31","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1007\/978-3-319-46376-6_9","article-title":"Structural properties of generalized exchanged hypercubes","author":"Cheng","year":"2017","journal-title":"Adamatzky, A. (ed.) Emergent Computation"},{"key":"2021011807350543000_ref32","first-page":"121","article-title":"Extraconnectivity of folded hypercubes","volume":"116","author":"Yang","year":"2014","journal-title":"Ars Combin."},{"key":"2021011807350543000_ref33","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1016\/j.tcs.2018.09.014","article-title":"The extra connectivity, extra conditional diagnosability and $t\/k$-diagnosability of the data center network DCell","volume":"766","author":"Li","year":"2019","journal-title":"Theor. Comput. Sci."},{"key":"2021011807350543000_ref34","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1109\/71.80187","article-title":"Properties and performance of folded hypercubes","volume":"2","author":"El-Amawy","year":"1991","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"2021011807350543000_ref35","doi-asserted-by":"crossref","first-page":"1782","DOI":"10.1016\/j.ins.2006.11.003","article-title":"On reliability of the folded hypercubes","volume":"177","author":"Zhu","year":"2007","journal-title":"Inform. Sci."},{"key":"2021011807350543000_ref36","first-page":"51","article-title":"Dual-cubes: a new interconnection network for high-performance computer clusters","author":"Li","year":"2000","journal-title":"Proc. ICS\u201900"},{"key":"2021011807350543000_ref37","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.tcs.2012.12.009","article-title":"Linearly many faults in dual-cube-like networks","volume":"472","author":"Angjeli","year":"2013","journal-title":"Theor. Comput. Sci."},{"key":"2021011807350543000_ref38","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1109\/71.262585","article-title":"The hierarchical hypercube: a new interconnection topology for massively parallel systems","volume":"5","author":"Malluhi","year":"1994","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"2021011807350543000_ref39","doi-asserted-by":"crossref","first-page":"300","DOI":"10.1145\/358645.358660","article-title":"The cube-connected-cycles: a versatile network for parallel computation","volume":"24","author":"Preparata","year":"1981","journal-title":"Commun. ACM."},{"key":"2021011807350543000_ref40","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":"Inform. Sci."},{"key":"2021011807350543000_ref41","doi-asserted-by":"crossref","first-page":"2152","DOI":"10.1080\/00207160.2012.710325","article-title":"Conditional fault diagnosis of hierarchical hypercubes","volume":"89","author":"Zhou","year":"2012","journal-title":"Int. J. Comput. Math."},{"key":"2021011807350543000_ref42","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1080\/00207160500113173","article-title":"On the maximal connected component of a hypercube with faulty vertices III","volume":"83","author":"Yang","year":"2006","journal-title":"Int. J. Comput. Math."},{"key":"2021011807350543000_ref43","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":"Inform. Process. Lett."},{"key":"2021011807350543000_ref44","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":"2018","journal-title":"J. Interconnect. Netw."},{"key":"2021011807350543000_ref45","doi-asserted-by":"crossref","first-page":"1248","DOI":"10.1109\/TR.2016.2570559","article-title":"The extra connectivity, extra conditional diagnosability, and $t\/m$-diagnosability of arrangement graphs","volume":"65","author":"Xu","year":"2016","journal-title":"IEEE Trans. Rel."},{"key":"2021011807350543000_ref46","doi-asserted-by":"crossref","first-page":"533","DOI":"10.1109\/TPDS.2015.2400459","article-title":"The extra connectivity, restricted connectivity and conditional diagnosability of split-star networks","volume":"27","author":"Lin","year":"2016","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"2021011807350543000_ref47","doi-asserted-by":"crossref","first-page":"2352","DOI":"10.1109\/TPDS.2014.2347961","article-title":"The extra connectivity and conditional diagnosability of alternating group networks","volume":"26","author":"Lin","year":"2015","journal-title":"IEEE Trans. Parallel Distrib. Syst."}],"container-title":["The Computer Journal"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/comjnl\/article-pdf\/64\/1\/38\/35886308\/bxz136.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"http:\/\/academic.oup.com\/comjnl\/article-pdf\/64\/1\/38\/35886308\/bxz136.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,1,18]],"date-time":"2021-01-18T14:01:25Z","timestamp":1610978485000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comjnl\/article\/64\/1\/38\/5644395"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,2,15]]},"references-count":47,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2020,2,15]]},"published-print":{"date-parts":[[2021,1,19]]}},"URL":"https:\/\/doi.org\/10.1093\/comjnl\/bxz136","relation":{},"ISSN":["0010-4620","1460-2067"],"issn-type":[{"value":"0010-4620","type":"print"},{"value":"1460-2067","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2021,1]]},"published":{"date-parts":[[2020,2,15]]}}}