The Maximum Number of Disjoint Paths in Faulty Enhanced Hypercubes

Abstract

The maximum number of internal disjoint paths between any two distinct nodes of faulty enhanced hypercube $Q_{n,k}(1\le k\le n-1)$ are considered in a more flexible approach. Using the structural properties of $Q_{n,k}(1\le k\le 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\ge 8,k\ne n-2,n-1)$ are conformed when $|V^{\prime }|$ 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\ge 8,k\ne 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^{\prime }$ is incident to at least two fault-free vertices. This results generalize the results of the faulted hypercube $F{Q}_n$, which is a special case of $Q_{n,k}$, and have improved the 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 improving the performance of the interconnect networks.