Many-to-Many Disjoint Paths in Augmented Cubes With Exponential Fault Edges
Mingzu Zhang, Wenhuan Ma, Tianlong Ma · IEEE Access · 2021
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 (λ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 AQnis a variant of hypercube Qn. 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 ≤ 2n-1, and that the g-extra edge-connectivity of AQn( n ≥ 3) concentrates on ⌈n/2⌉-1 special values. Specifically, we prove that the exact value of g-extra edge-connectivity of augmented cube is a constant 2(⌈n/2⌉-r)2⌈n/2⌉+rfor each integer 2⌈n/2⌉+r-lr≤ g ≤ 2⌈n/2⌉+r, where n ≥ 3, r=1, 2, ..., ⌈ n/2⌉-1 and lr=\frac 22r+1-23 if n is odd and lr=\frac 22r+2-43 if n is even. The above upper and lower bounds of g are sharp. Moreover, we also obtain the exponential edge disjoint paths in AQnwith edge faults.