A connected graph $G$ is called strongly Menger (edge) connected if for any two distinct vertices $x,y$ of $G$, there are $min {{rm deg}_G(x), {rm deg}_G(y)}$ vertex(edge)-disjoint paths between $x$ and $y$. 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}$ for $ngeq 4$ (resp. $AQ_{n,k}$ for $ngeq 2$ and $kgeq 4$) is still strongly Menger connected even when there are $4n-9$ (resp. $4n-8$) faulty vertices and $AQ_{n,k}$ is still strongly Menger edge connected even when there are $4n-4$ faulty edges for $ngeq 2$ and $kgeq 3$. Moreover, under the restricted condition that each vertex has at least two fault-free edges, we show that $AQ_{n,k}$ is still strongly Menger edge connected even when there are $8n-10$ faulty edges for $ngeq 2$ and $kgeq 3$. These results are all optimal in the sense of the maximum number of tolerated vertex (resp. edge) faults.
Download