Partitions of faulty hypercubes into paths with prescribed endvertices

Abstract

We study the existence of a path partition with prescribed endvertices in faulty hypercubes. We show that an obvious necessary condition for the existence of such a partition is also sufficient provided the number of faults and prescribed endvertices is small.

As a corollary, we obtain a similar characterization for the existence of a hamiltonian cycle and a hamiltonian path of faulty hypercube. On the other hand, if the number of faults is not limited, the problems are NP-complete.

Keywords

• Partitions
• faulty
• hypercubes
• paths
• prescribed
• endvertices