Fault-Tolerant Mutually Independent Hamiltonian Cycles Embedding on Hypercubes
Sun‐Yuan Hsieh · 2006
A Hamiltonian path (respectively, cycle) in G is a path (respectively, cycle) which contains every vertex of G exactly once. Two Hamiltonian paths in a graph G, P_1 = (u_1, u_2..., u_n) and P_2 = (v_1, v_2,..., v_n), are full-independent if u_i e v_i for every 1 \leqslant= i \leqslant n. A set of Hamiltonian paths {P_1, P_2,..., P_k} of G are mutually full-independent if any two different Hamiltonian paths in the set are full-independent. On the other hand, two Hamiltonian cycles, C_1 = (u_1, u_2,..., u_n, u_1) and C_2 = (v_1, v_2, ..., v_n, v_1), are independent starting at u_1 if u_1 = v_1 and u_i e v_i for every 1 \le i \le n. A set of Hamiltonian cycles {C_1, C_2,..., C_k} of G are mutually independent starting at v if any two different Hamiltonian cycles in the set are independent starting at v. Let F be the set of faulty edges of Qn such that 1 \leqslant |F| \leqslant n - 2. In this paper, we show that Q_n - F contains n - |F| - 1 fault-free mutually full-independent Hamiltonian paths between two adjacent vertices, where n \geqslant 3. We also show that Qn contains n - |F| - 1 fault-free mutually independent Hamiltonian cycles starting at any vertex, where n \geqslant 4.