Partitions of Faulty Hypercubes into Paths with Prescribed Endvertices
Tomáš Dvořák, Petr Gregor · SIAM Journal on Discrete Mathematics · 2008
Given a set $\pc=\{a_i,b_i\}_{i=1}^m$ of pairs of vertices in a graph G, is there a collection of paths $\{P_i\}_{i=1}^m$ such that $P_i$ connects $a_i$ with $b_i$ and $\{V(P_i)\}_{i=1}^m$ partitions $V(G)$? We study this problem for the graph $Q_n-\ff$ obtained from the n-dimensional hypercube $Q_n$ by removing a set $\ff$ of faulty vertices. We show that an obvious necessary condition for the existence of such a partition is also sufficient provided $2|\pc|+ 3|\ff|\le n-3$. As a corollary, we obtain a similar characterization for the existence of a hamiltonian cycle and a hamiltonian path of $Q_n-\ff$ provided $|\ff|\le(n-5)/3$. On the other hand, if the size of $\ff$ is not limited, the problems are NP-complete.