Strong Menger Connectedness of Augmented k-ary n-cubes. (9th May 2020)

• Record Type: Journal Article
• Authors: Gu, Mei-Mei; Chang, Jou-Ming; Hao, Rong-Xia
• Is Part Of: Computer journal. Volume 64:Number 5(2021)
• Page Start: 812
• Page End: 825
• Publication Date: 2020-05-09
• Subjects: Strong Menger edge connectivity -- maximal local-connectivity -- augmented k-ary n-cubes -- fault-tolerance; Computers -- Periodicals; 005.1
• DOI: 10.1093/comjnl/bxaa037
• Languages: English
• ISSNs: 0010-4620

Abstract

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.