Strong Menger Connectedness of Augmented k-ary n-cubes

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 subset of V(G) (resp. edge set F subset of E(G)) with vertical bar F vertical bar <= 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 subset of V(G) (resp. edge set F subset of E(G)) with vertical bar F vertical bar <= m and delta(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.

Automated summary

This paper examines the strong Menger (edge) connectedness properties of graphs, exploring the topological features of the augmented k-ary n-cube. The results show that under certain conditions, specific graphs exhibit optimal connectivity, tolerating the maximum number of faults.