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 (1)=aOE (c) u (1),u (2),aEuro broken vertical bar,u (n) > and P (2)=aOE (c) v (1),v (2),aEuro broken vertical bar,v (n) > of G are said to be independent if u (1)=v (1), u (n) =v (n) , and u (i) not equal v (i) for all 1 < i < n; and both are full-independent if u (i) not equal v (i) for all 1a parts per thousand currency signia parts per thousand currency signn. Moreover, P (1) and P (2) are independent starting at u (1), if u (1)=v (1) and u (i) not equal v (i) for all 1 < ia parts per thousand currency signn. A set of Hamiltonian paths {P (1),P (2),aEuro broken vertical bar,P (k) } of G are pairwise independent (respectively, pairwise full-independent, pairwise independent starting at u (1)) if any two different Hamiltonian paths in the set are independent (respectively, full-independent, independent starting at u (1)). 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: When |F|a parts per thousand currency signn-4, Q (n) -F-{x,y} remains Hamiltonian-laceable, where x and y are any two vertices from different partite sets and na parts per thousand yen4. When |F|a parts per thousand currency signn-2, Q (n) -F contains (n-|F|-1)-pairwise full-independent Hamiltonian paths between n-|F|-1 pairs of adjacent vertices, where na parts per thousand yen2. When |F|a parts per thousand currency signn-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 na parts per thousand yen2. When 1a parts per thousand currency sign|F|a parts per thousand currency signn-2, Q (n) -F contains (n-|F|-1)-pairwise independent Hamiltonian paths between any two vertices from different partite sets, where na parts per thousand yen3.