Strong Menger connectedness of augmented k-ary n-cubes
share
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)} 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 n≥ 4 (resp. AQ_n,k for n≥ 2 and k≥ 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 n≥ 2 and k≥ 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 n≥ 2 and k≥ 3. These results are all optimal in the sense of the maximum number of tolerated vertex (resp. edge) faults.
READ FULL TEXT