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

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 <inline-formula> <tex-math notation="LaTeX">$g$ </tex-math></inline-formula> vertices in <inline-formula> <tex-math notation="LaTeX">$G$ </tex-math></inline-formula> can also define by the minimum modified edge-cut, called the <inline-formula> <tex-math notation="LaTeX">$g$ </tex-math></inline-formula>-extra edge-connectivity of <inline-formula> <tex-math notation="LaTeX">$G~(\lambda _{g}(G))$ </tex-math></inline-formula>. It is the cardinality of the minimum set of edges in <inline-formula> <tex-math notation="LaTeX">$G$ </tex-math></inline-formula>, if such a set exists, whose deletion disconnects <inline-formula> <tex-math notation="LaTeX">$G$ </tex-math></inline-formula> and leaves every remaining component with at least <inline-formula> <tex-math notation="LaTeX">$g$ </tex-math></inline-formula> vertices. The <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula>-dimensional augmented cube <inline-formula> <tex-math notation="LaTeX">$AQ_{n}$ </tex-math></inline-formula> is a variant of hypercube <inline-formula> <tex-math notation="LaTeX">$Q_{n}$ </tex-math></inline-formula>. In this paper, we observe that the <inline-formula> <tex-math notation="LaTeX">$g$ </tex-math></inline-formula>-extra edge-connectivity of the augmented cube for some exponentially large enough <inline-formula> <tex-math notation="LaTeX">$g$ </tex-math></inline-formula> exists a concentration behavior, for about 72.22 percent values of <inline-formula> <tex-math notation="LaTeX">$g\leq 2^{n-1}$ </tex-math></inline-formula>, and that the <inline-formula> <tex-math notation="LaTeX">$g$ </tex-math></inline-formula>-extra edge-connectivity of <inline-formula> <tex-math notation="LaTeX">$AQ_{n}$ </tex-math></inline-formula> (<inline-formula> <tex-math notation="LaTeX">$n\geq 3$ </tex-math></inline-formula>) concentrates on <inline-formula> <tex-math notation="LaTeX">${\lceil \frac {n}{2}\rceil }-1$ </tex-math></inline-formula> special values. Specifically, we prove that the exact value of <inline-formula> <tex-math notation="LaTeX">$g$ </tex-math></inline-formula>-extra edge-connectivity of augmented cube is a constant <inline-formula> <tex-math notation="LaTeX">$2\left({{\lceil \frac {n}{2}\rceil }-r}\right)2^{{\lfloor \frac {n}{2}\rfloor }+r}$ </tex-math></inline-formula> for each integer <inline-formula> <tex-math notation="LaTeX">$2^{{\lfloor \frac {n}{2}\rfloor }+r}-l_{r}\leq g\leq 2^{{\lfloor \frac {n}{2}\rfloor }+r}$ </tex-math></inline-formula>, where <inline-formula> <tex-math notation="LaTeX">$n\geq 3$ </tex-math></inline-formula>, <inline-formula> <tex-math notation="LaTeX">$r=1, 2, \ldots, {\lceil \frac {n}{2}\rceil }-1$ </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">$l_{r}=\frac {2^{2r+1}-2}{3}$ </tex-math></inline-formula> if <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula> is odd and <inline-formula> <tex-math notation="LaTeX">$l_{r}=\frac {2^{2r+2}-4}{3}$ </tex-math></inline-formula> if <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula> is even. The above upper and lower bounds of <inline-formula> <tex-math notation="LaTeX">$g$ </tex-math></inline-formula> are sharp. Moreover, we also obtain the exponential edge disjoint paths in <inline-formula> <tex-math notation="LaTeX">$AQ_{n}$ </tex-math></inline-formula> with edge faults.

Abstract licence: CC BY-NC-ND

A person counts once a day per paper. We keep no cookie and no address: a reader is a hash that changes every day. Any month under five reads shows no number.