Fault-Tolerant Embedding of Pairwise Independent Hamiltonian Paths on a Faulty Hypercube with Edge Faults

A Hamiltonian path in G is a path which contains every vertex of G exactly once. Two Hamiltonian paths P1=〈u1,u2,…,un〉 and P2=〈v1,v2,…,vn〉 of G are said to be independent if u1=v1, un=vn, and ui≠vi for all 1<i<n; and both are full-independent if ui≠vi for all 1≤i≤n. Moreover, P1 and P2 are independent starting atu1, if u1=v1 and ui≠vi for all 1<i≤n. A set of Hamiltonian paths {P1,P2,…,Pk} of G are pairwise independent (respectively, pairwise full-independent, pairwise independent starting atu1) if any two different Hamiltonian paths in the set are independent (respectively, full-independent, independent starting at u1). A bipartite graph G is Hamiltonian-laceable if there exists a Hamiltonian path between any two vertices from different partite sets. It is well known that an n-dimensional hypercube Qn is bipartite with two partite sets of equal size. Let F be the set of faulty edges of Qn. In this paper, we show the following results: When |F|≤n−4, Qn−F−{x,y} remains Hamiltonian-laceable, where x and y are any two vertices from different partite sets and n≥4.When |F|≤n−2, Qn−F contains (n−|F|−1)-pairwise full-independent Hamiltonian paths between n−|F|−1 pairs of adjacent vertices, where n≥2.When |F|≤n−2, Qn−F contains (n−|F|−1)-pairwise independent Hamiltonian paths starting at any vertex v in a partite set to n−|F|−1 distinct vertices in the other partite set, where n≥2.When 1≤|F|≤n−2, Qn−F contains (n−|F|−1)-pairwise independent Hamiltonian paths between any two vertices from different partite sets, where n≥3.