Hamiltonian cycles and paths in hypercubes with disjoint faulty edges (Q2234783)

The paper shows that the hypercube \(Q_n\) of dimension \(n\ge 4\) with disjoint faulty edges (i.e., a faulty matching) is Hamiltonian if and only if for each direction there is at least one healthy edge of each parity. The \textit{direction} of an edge \(\{x,y\}\in E(Q_n)\) is defined as the position where the binary strings \(x\), \(y\) differ, and the \textit{parity} of \(\{x,y\}\) is the parity of the vertex that has \(0\) on this position. These results have already been proved in [\textit{D. Dimitrov} et al., Discrete Math. Theor. Comput. Sci. 11, No. 2, 123--147 (2009; Zbl 1192.94070), see Corollary~1]. Furthermore, the paper shows that the hypercube \(Q_n\) with \(n\ge 4\) with disjoint faulty edges is Hamilton-laceable if for each direction there are at least three healthy edges and they are not of the same parity. A bipartite graph is said to be \textit{Hamilton-laceable} if there is a Hamilton path between any two vertices from different bipartite classes. However, the above paper by Dimitrov et al. presents a stronger condition that is both necessary and sufficient, see Theorem~1 of [Zbl 1192.94070].