{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T17:37:24Z","timestamp":1770917844419,"version":"3.50.1"},"reference-count":22,"publisher":"Oxford University Press (OUP)","issue":"5","license":[{"start":{"date-parts":[[2020,5,9]],"date-time":"2020-05-09T00:00:00Z","timestamp":1588982400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021,5,19]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>A connected graph $G$ is called strongly Menger (edge) connected if for any two distinct vertices $x,y$ of $G$, there are $\\min \\{\\textrm{deg}_G(x), \\textrm{deg}_G(y)\\}$ internally disjoint (edge disjoint) paths between $x$ and $y$. Motivated by parallel routing in networks with faults, Oh and Chen (resp., Qiao and Yang) proposed the (fault-tolerant) strong Menger (edge) connectivity as follows. A graph $G$ is called $m$-strongly Menger (edge) connected if $G-F$ remains strongly Menger (edge) connected for an arbitrary vertex set $F\\subseteq V(G)$ (resp. edge set $F\\subseteq E(G)$) with $|F|\\leq m$. A graph $G$ is called $m$-conditional strongly Menger (edge) connected if $G-F$ remains strongly Menger (edge) connected for an arbitrary vertex set $F\\subseteq V(G)$ (resp. edge set $F\\subseteq E(G)$) with $|F|\\leq m$ and $\\delta (G-F)\\geq 2$. In this paper, we consider strong Menger (edge) connectedness of the augmented $k$-ary $n$-cube $AQ_{n,k}$, which is a variant of $k$-ary $n$-cube $Q_n^k$. By exploring the topological proprieties of $AQ_{n,k}$, we show that $AQ_{n,3}$ (resp. $AQ_{n,k}$, $k\\geq 4$) is $(4n-9)$-strongly (resp. $(4n-8)$-strongly) Menger connected for $n\\geq 4$ (resp. $n\\geq 2$) and $AQ_{n,k}$ is $(4n-4)$-strongly Menger edge connected for $n\\geq 2$ and $k\\geq 3$. Moreover, we obtain that $AQ_{n,k}$ is $(8n-10)$-conditional strongly Menger edge connected for $n\\geq 2$ and $k\\geq 3$. These results are all optimal in the sense of the maximum number of tolerated vertex (resp. edge) faults.<\/jats:p>","DOI":"10.1093\/comjnl\/bxaa037","type":"journal-article","created":{"date-parts":[[2020,5,9]],"date-time":"2020-05-09T11:37:55Z","timestamp":1589024275000},"page":"812-825","source":"Crossref","is-referenced-by-count":23,"title":["Strong Menger Connectedness of Augmented <i>k<\/i>-ary <i>n<\/i>-cubes"],"prefix":"10.1093","volume":"64","author":[{"given":"Mei-Mei","family":"Gu","sequence":"first","affiliation":[{"name":"Department of Mathematics, Beijing Jiaotong University, Beijing 100044, P.R. China"},{"name":"Faculty of Mathematics and Physics, Charles University, Prague 11800, Czech Republic"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jou-Ming","family":"Chang","sequence":"additional","affiliation":[{"name":"Institute of Information and Decision Sciences, National Taipei University of Business, Taipei 10051, Taiwan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rong-Xia","family":"Hao","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Beijing Jiaotong University, Beijing 100044, P.R. China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2020,5,9]]},"reference":[{"key":"2021052810194635500_ref1","doi-asserted-by":"crossref","first-page":"95","DOI":"10.4064\/fm-10-1-96-115","article-title":"Zur allgemeinen kurventheorie","volume":"10","author":"Menger","year":"1927","journal-title":"Fund. Math."},{"key":"2021052810194635500_ref2","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1016\/j.dam.2014.10.006","article-title":"Fault-tolerant maximal local-connectivity on Bubble-sort star graphs","volume":"181","author":"Cai","year":"2015","journal-title":"Discrete Appl. Math."},{"key":"2021052810194635500_ref3","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1016\/j.ins.2014.03.022","article-title":"Maximally local connectivity and connected components of augmented cubes","volume":"273","author":"Chen","year":"2014","journal-title":"Inform. Sci."},{"key":"2021052810194635500_ref4","doi-asserted-by":"crossref","first-page":"84","DOI":"10.1016\/j.ipl.2018.10.019","article-title":"Parallel routing in regular networks with faults","volume":"142","author":"Sabir","year":"2019","journal-title":"Inform. Proces. Lett."},{"key":"2021052810194635500_ref5","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/j.tcs.2019.06.016","article-title":"The $t\/k$-diagnosability and strong Menger connectivity on star graphs with conditional faults","volume":"793","author":"Li","year":"2019","journal-title":"Theoret. Comput. Sci."},{"key":"2021052810194635500_ref6","doi-asserted-by":"crossref","first-page":"499","DOI":"10.1016\/S0166-218X(02)00600-5","article-title":"On strong Menger-connectivity of star graphs","volume":"129","author":"Oh","year":"2003","journal-title":"Discrete Appl. Math."},{"key":"2021052810194635500_ref7","article-title":"On strong fault tolerance (or strong Menger-connectivity) of multicomputer networks","author":"Oh","year":"2004"},{"key":"2021052810194635500_ref8","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1016\/j.ipl.2017.05.001","article-title":"Strong Menger connectivity with conditional faults of folded hypercubes","volume":"125","author":"Yang","year":"2017","journal-title":"Inform. Process. Lett."},{"key":"2021052810194635500_ref9","doi-asserted-by":"crossref","first-page":"64","DOI":"10.1016\/j.ipl.2007.10.009","article-title":"Strong Menger connectivity with conditional faults on the class of hypercube-like networks","volume":"106","author":"Shih","year":"2008","journal-title":"Inform. Process. Lett."},{"key":"2021052810194635500_ref10","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1142\/S021926590900256X","article-title":"Fault-tolerant maximal local-connectivity on Cayley graphs generated by transposition trees","volume":"10","author":"Shih","year":"2009","journal-title":"J. Interconnect. Netw."},{"key":"2021052810194635500_ref11","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1016\/j.tcs.2017.10.017","article-title":"Fault-tolerant strong Menger (edge) connectivity and 3-extra edge-connectivity of balanced hypercubes","volume":"707","author":"Li","year":"2018","journal-title":"Theoret. Comput. Sci."},{"key":"2021052810194635500_ref12","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1016\/j.amc.2016.09.002","article-title":"Edge disjoint paths in hypercubes and folded hypercubes with conditional faults","volume":"294","author":"Qiao","year":"2017","journal-title":"Appl. Math. Comput."},{"key":"2021052810194635500_ref13","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.tcs.2018.03.011","article-title":"Conditional (edge) fault-tolerant strong Menger (edge) connectivity of folded hypercubes","volume":"728","author":"Cheng","year":"2018","journal-title":"Theoret. Comput. Sci."},{"key":"2021052810194635500_ref14","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1016\/j.dam.2018.12.024","article-title":"Edge-fault-tolerant strong Menger edge connectivity on the class of hypercube-like networks","volume":"259","author":"Li","year":"2019","journal-title":"Discrete Appl. Math."},{"key":"2021052810194635500_ref15","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1016\/j.tcs.2018.04.001","article-title":"Strongly Menger-edge-connectedness and strongly Menger-vertex-connectedness of regular networks","volume":"731","author":"He","year":"2018","journal-title":"Theoret. Comput. Sci."},{"key":"2021052810194635500_ref16","doi-asserted-by":"crossref","first-page":"94","DOI":"10.1016\/j.tcs.2019.09.047","article-title":"Strongly Menger connectedness of data center network and $(n,k)$-star graph","volume":"799","author":"Gu","year":"2019","journal-title":"Theoret. Comput. Sci."},{"key":"2021052810194635500_ref17","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1016\/j.ins.2010.09.005","article-title":"Augmented $k$-ary $n$-cubes","volume":"181","author":"Xiang","year":"2011","journal-title":"Inform. Sci."},{"key":"2021052810194635500_ref18","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1002\/net.10033","article-title":"Augmented cubes","volume":"40","author":"Choudum","year":"2002","journal-title":"Networks"},{"key":"2021052810194635500_ref19","first-page":"98","article-title":"The pessimistic diagnosability of bubble-sort star graphs and augmented $k$-ary $n$-cubes","volume":"1","author":"Gu","year":"2016","journal-title":"Int. J. Comput. Math.: Comput. Sys. Theory"},{"key":"2021052810194635500_ref20","doi-asserted-by":"crossref","first-page":"1281","DOI":"10.1080\/00207160.2015.1067690","article-title":"The restricted edge-connectivity and restricted connectivity of augmented $k$-ary $n$-cubes","volume":"93","author":"Lin","year":"2016","journal-title":"Inter. J. Comput. Math."},{"key":"2021052810194635500_ref21","first-page":"308","article-title":"Pancyclicity and panconnectivity in augmented $k$-ary $n$-cubes","author":"Xiang","year":"2009","journal-title":"IEEE 15th Int. Conf. on Parallel and Distributed Systems (ICPADS)"},{"key":"2021052810194635500_ref22","first-page":"1","article-title":"The two-good-neighbor connectivity and diagnosability of the augmented three-ary $n$-cubes","volume":"63","author":"Wang","year":"2020","journal-title":"Comput. J."}],"container-title":["The Computer Journal"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/comjnl\/article-pdf\/64\/5\/812\/38334996\/bxaa037.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"http:\/\/academic.oup.com\/comjnl\/article-pdf\/64\/5\/812\/38334996\/bxaa037.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,28]],"date-time":"2021-05-28T11:52:39Z","timestamp":1622202759000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comjnl\/article\/64\/5\/812\/5830802"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,5,9]]},"references-count":22,"journal-issue":{"issue":"5","published-online":{"date-parts":[[2020,5,9]]},"published-print":{"date-parts":[[2021,5,19]]}},"URL":"https:\/\/doi.org\/10.1093\/comjnl\/bxaa037","relation":{},"ISSN":["0010-4620","1460-2067"],"issn-type":[{"value":"0010-4620","type":"print"},{"value":"1460-2067","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2021,5]]},"published":{"date-parts":[[2020,5,9]]}}}