Paired many-to-many disjoint path covers of hypercubes with faulty edges

Let Mk={ui,vi}i=1k be a set of k pairs of distinct vertices of the n  -dimensional hypercube QnQn such that it contains k   vertices from each class of bipartition of QnQn. Gregor and Dvořák proved that if n>2kn>2k, then there exist k   vertex-disjoint paths P1,P2,…,PkP1,P2,…,Pk containing all vertices of QnQn, where two end-vertices of PiPi are uiui and vivi for i=1,2,…,ki=1,2,…,k. In this paper we show that the result still holds if removing n−2k−1n−2k−1 edges from QnQn. When k=2k=2, we also show that the result still holds if removing 2n−7⩾12n−7⩾1 edges from QnQn such that every vertex is incident with at least three fault-free edges, and the number 2n−72n−7 of faulty edges tolerated is sharp.

► Let {ui,vi}i=1k be a balanced set of vertices in an n  -cube QnQn with n>2kn>2k. ► Then there exist k   vertex-disjoint ui−viui−vi paths covering QnQn if removing n−2k−1n−2k−1 edges from QnQn. ► When k=2k=2, the above result still holds if removing 2n−72n−7 edges and minimum degree δ>2δ>2. ► The number 2n−72n−7 of faulty edges tolerated is sharp.