2013/12/06 by Castañeda, Nelson, Gotchev, Ivan S. · 1 citation
#05C45 #68M10 #68M15 #Combinatorics (math.CO) #FOS: Mathematics #Primary 05C38 #Secondary 68R10
paper · doi:10.48550/arxiv.1312.1880
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.