Many-to-Many Disjoint Paths in Augmented Cubes With Exponential Fault Edges

Abstract

It is common knowledge that edge disjoint paths have close relationship with the edge connectivity. Motivated by the well-known Menger theorem, we find that the maximum cardinality of edge disjoint paths connecting any two disjoint connected subgraphs with $g$ vertices in $G$ can also define by the minimum modified edge-cut, called the $g$ -extra edge-connectivity of $G~(\lambda _{g}(G))$ . It is the cardinality of the minimum set of edges in $G$ , if such a set exists, whose deletion disconnects $G$ and leaves every remaining component with at least $g$ vertices. The $n$ -dimensional augmented cube $AQ_{n}$ is a variant of hypercube $Q_{n}$ . In this paper, we observe that the $g$ -extra edge-connectivity of the augmented cube for some exponentially large enough $g$ exists a concentration behavior, for about 72.22 percent values of $g\leq 2^{n-1}$ , and that the $g$ -extra edge-connectivity of $AQ_{n}$ ( $n\geq 3$ ) concentrates on ${\lceil \frac {n}{2}\rceil }-1$ special values. Specifically, we prove that the exact value of $g$ -extra edge-connectivity of augmented cube is a constant $2\left({{\lceil \frac {n}{2}\rceil }-r}\right)2^{{\lfloor \frac {n}{2}\rfloor }+r}$ for each integer $2^{{\lfloor \frac {n}{2}\rfloor }+r}-l_{r}\leq g\leq 2^{{\lfloor \frac {n}{2}\rfloor }+r}$ , where $n\geq 3$ , $r=1, 2, \ldots, {\lceil \frac {n}{2}\rceil }-1$ and $l_{r}=\frac {2^{2r+1}-2}{3}$ if $n$ is odd and $l_{r}=\frac {2^{2r+2}-4}{3}$ if $n$ is even. The above upper and lower bounds of $g$ are sharp. Moreover, we also obtain the exponential edge disjoint paths in $AQ_{n}$ with edge faults.

Keywords

• Fault tolerance
• many-to-many edge disjoint paths
• interconnected networks
• exponential fault edges