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 P₁=« u₁,u ₂,u_n » and P₂=«v₁,v ₂,v_n » of G are said to be independent if u ₁=v₁, u_n =v_n , and u_i ≠v_i for all 1<i<n; and both are full-independent if u _i ≠v_i for all 1≤in. Moreover, P₁ and P₂ are independent starting at u₁, if u₁=v ₁ and u_i ≠v_i for all 1<i≤n. A set of Hamiltonian paths {P₁,P₂,P_k } of G are pairwise independent (respectively, pairwise full-independent, pairwise independent starting at u₁) if any two different Hamiltonian paths in the set are independent (respectively, full-independent, independent starting at u ₁). 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 Q_n is bipartite with two partite sets of equal size. Let F be the set of faulty edges of Q_n . In this paper, we show the following results: 1. When |F|≤n-4, Q_n -F-{x,y} remains Hamiltonian-laceable, where x and y are any two vertices from different partite sets and n≥4. 2. When |F|≤n-2, Q_n -F contains (n-|F|-1)-pairwise full-independent Hamiltonian paths between n-|F|-1 pairs of adjacent vertices, where n≥2. 3. When |F|≤n-2, Q_n -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. 4. When 1≤|F|≤n-2, Q_n -F contains (n-|F|-1)-pairwise independent Hamiltonian paths between any two vertices from different partite sets, where n≥3.