Strong Menger Connectedness of Augmented k-ary n-cubes. (9th May 2020) - Gu, Mei-Mei; Chang, Jou-Ming; Hao, Rong-Xia
Abstract: A connected graph $G$ is called strongly Menger (edge) connected if for any two distinct vertices $x, y$ of $G$, there are $\min \{deg_G(x), 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|≤ 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|≤ m$ and $δ (G-F)≥ 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≥ 4$ ) is $(4n-9)$ -strongly (resp. $(4n-8)$ -strongly) Menger connected for $n≥ 4$ (resp. $n≥ 2$ ) and $AQ_{n, k}$ is $(4n-4)$ -strongly Menger edge connected for $n≥ 2$ and $k≥ 3$ . Moreover, we obtain that $AQ_{n, k}$ is $(8n-10)$ -conditional strongly Menger edge connected for $n≥ 2$ and $k≥ 3$ . These results are all optimal in the sense of the maximum number of tolerated vertex (resp. edge) faults.