Paired many-to-many disjoint path covers of hypercubes with faulty edges
Let M-k = {u(i), v(i)}(i=1)(k), be a set of k pairs of distinct vertices of the n-dimensional hypercube Q(n) such that it contains k vertices from each class of bipartition of Q(n). Gregor and Dvorak proved that if n > 2k, then there exist k vertex-disjoint paths P-1, P-2,..., P-k. containing all vertices of Q(n), where two end-vertices of P-i are u(i) and v(i) for i = 1, 2,..., k. In this paper we show that the result still holds if removing n - 2k - 1 edges from Q(n). When k = 2, we also show that the result still holds if removing 2n - 7 >= 1 edges from Qn such that every vertex is incident with at least three fault-free edges, and the number 2n - 7 of faulty edges tolerated is sharp. (C) 2011 Elsevier B.V. All rights reserved.
cover hypercube vertex-disjoint paths hamiltonian path fault tolerance interconnection networks