Hamiltonian cycles and paths in hypercubes with disjoint faulty edges

We consider hypercubes with pairwise disjoint faulty edges. An n-dimensional hypercube Q(n) is an undirected graph with 2(n) nodes, each labeled with a distinct binary string of length n. The parity of the vertex is 0 if the number of ones in its label is even, and is 1 if the number of ones is odd. Two vertices a and b are connected by an edge iff a and b differ in one position. If a and b differ in position i, then we say that the edge (a, b) goes in dimension i and we define the parity of the edge as the parity of the end with 0 on the position i. It was already known that Q(n) is not Hamiltonian if all edges going in one dimension and of the same parity are faulty. In this paper we show that if n >= 4 then all other hypercubes are Hamiltonian. In other words, every cube Q(n), with n >= 4 and disjoint faulty edges is Hamiltonian if and only if for each dimension there are two healthy crossing edges of different parity. (C) 2021 Elsevier B.V. All rights reserved.

Automated summary

This paper investigates hypercubes with pairwise disjoint faulty edges and proves that all other hypercubes are Hamiltonian when n >= 4, as long as there are two healthy crossing edges of different parity in each dimension.