HAMILTONIAN LACEABILITY OF FAULTY HYPERCUBES
Chao-Ming Sun, Chun‐Nan Hung, Hua‐Min Huang, Lih‐Hsing Hsu, Yue‐Dar Jou · Journal of Interconnection Networks · 2007
We consider the occurrence of the combination of edge faults and vertex faults in hypercubes. To preserve the equitability of Qn, we restrict the faults on vertex occurring only on disjoint adjacent pairs. Let F be a subset of V(Qn) ∪ E(Qn) such that F can be decomposed into two parts Fav and Fe where Fav is a union of fav disjoint adjacent pairs of Qn and Fe consists of fe edges of Qn. We show that the Qn - F is still hamiltonian if fav + fe ≤ n - 2. In addition, we prove that there exists a hamiltonian path in Qn - {v} - F between any two vertices in the partite set not containing v if fav + fe ≤ n - 3. Furthermore, all bounds are tight. This generalizes a recent result of Fu (2006).