The Maximum Number of Disjoint Paths in Faulty Enhanced Hypercubes

摘要

The maximum number of internal disjoint paths between any two distinct nodes of faulty enhanced hypercube Q_(n,k)(1 ≤ k ≤ n - 1) are considered in a more flexible approach. Using the structural properties of Q_(n,k)(1 ≤ k ≤ n - 1), min{d_(Q_(n,k)-v'(x).d_(Q_(n,k)-v'(y)} disjoint paths connecting two distinct vertices x and y in an n-dimensional faulty enhanced hypercube Q_(n,k) - V'(n > 8, k ≠ n -2,n - 1) are conformed when |V'| is at most n - 1. Meanwhile, it is proved that there exists min{d_(Q_(n,k)-v'(x), d_(Q_(n,k)-v'(y)} internal disjoint paths between x and y in Q_(n,k) - V'(n > 8, k ≠ n - 2,n - 1), under the constraints that (1) The number of faulty vertices is no more than 2n - 3; (2) every vertex in Q_(n,k)-V' is incident to at least two fault-free vertices. This results generalize the results of folded hypercube FQ_n which is a special case of Q_(n,k), and have improved the present results with further theoretical evidence of the fact that Q_(n,k) has excellent node-fault-tolerance when used as a topology of large scale computer networks, thus remarkably improve the performance of the interconnect networks.