Path Coverings with Prescribed Ends in Faulty Hypercubes
2015
We discuss the existence of vertex disjoint path coverings with prescribed ends for the $$n$$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$$m such that for every $$n \ge m$$n?m such path coverings exist. Using some of these results, for $$k \le 4$$k≤4, we prove Locke's conjecture that a hypercube with $$k$$k deleted vertices of each parity is Hamiltonian if $$n \ge k +2.$$n?k+2. Some of our lemmas substantially generalize known results of I. Havel and T. Dvořak. At the end of the paper we formulate some conjectures supported by our results.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
12
References
6
Citations
NaN
KQI