Strong Menger connectedness of augmented $k$-ary $n$-cubes

Abstract

A connected graph $G$ is called strongly Menger (edge) connected if for any two distinct vertices $x,y$ of $G$, there are $\min \{{\mathrm{deg}}_G(x),{\mathrm{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 $A{Q}_{n,k}$, which is a variant of $k$-ary $n$-cube $Q_n^k$. By exploring the topological proprieties of $A{Q}_{n,k}$, we show that $A{Q}_{n,3}$ for $n\ge 4$ (resp.\ $A{Q}_{n,k}$ for $n\ge 2$ and $k\ge 4$) is still strongly Menger connected even when there are $4n-9$ (resp.\ $4n-8$) faulty vertices and $A{Q}_{n,k}$ is still strongly Menger edge connected even when there are $4n-4$ faulty edges for $n\ge 2$ and $k\ge 3$. Moreover, under the restricted condition that each vertex has at least two fault-free edges, we show that $A{Q}_{n,k}$ is still strongly Menger edge connected even when there are $8n-10$ faulty edges for $n\ge 2$ and $k\ge 3$. These results are all optimal in the sense of the maximum number of tolerated vertex (resp.\ edge) faults.

18 pages, 4 figures