Strong Menger Connectedness of Augmented k-ary n-cubes

Abstract

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.