PATH COVERINGS WITH PRESCRIBED ENDS IN FAULTY HYPERCUBES

Abstract. We discuss the existence of vertex disjoint path coverings with prescribed ends for the n-dimensional hypercube with or without deleted vertices. Depending on the type of the set of deleted vertices and desired properties of the path coverings we establish the minimal integer m such that for every n ≥ m such path coverings exist. Using some of these results, for k ≤ 4, we prove Locke’s conjecture that a hypercube with k deleted vertices of each parity is Hamiltonian if n ≥ k + 2. Some of our lemmas substantially generalize known results of I. Havel and T. Dvořák. At the end of the paper we formulate some conjectures supported by our results. 1