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 {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 FV(G) (resp. edge set FE(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 FV(G) (resp. edge set FE(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.