HAMILTONIAN LACEABILITY OF HYPERCUBES WITH FAULTS OF CHARGE ONE

摘要

In 2007, in their paper Path coverings with prescribed ends in faulty hypercubes, N. Castaneda and I. Gotchev formulated the following conjecture: Let n and k be positive integers with n ≥ k + 3 and F be a set of k even (odd) and k + 1 odd (even) vertices in the binary hypercube Q_n. If u_1 and u_2 are two distinct even (odd) vertices in Q_n - F then for Q_n - F there exists a Hamiltonian path that connects u_1 to u_2. In the same paper Castaneda and Gotchev proved that conjecture for k = 1 and k = 2. Here we provide a proof for k = 3.