Path coverings with prescribed ends in faulty hypercubes
classification
🧮 math.CO
keywords
coveringspathdeletedresultssomeverticesendshypercube
read the original 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 \ge m$ such path coverings exist. Using some of these results, for $k \le 4$, we prove Locke's conjecture that a hypercube with $k$ deleted vertices of each parity is Hamiltonian if $n \ge k +2.$ Some of our lemmas substantially generalize known results of I. Havel and T. Dvo\v{r}\'{a}k. At the end of the paper we formulate some conjectures supported by our results.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.