Spanning multi-paths in hypercubes (Q2370445)

It is well known that two vertices of the \(n\)-dimensional hypercube \(Q_n\) are connected by a Hamiltonian path if and only if they belong to different partite classes of \(Q_n\) [\textit{I.~Havel}, Čas. Pěst. Mat.~109, 135-152 (1984; Zbl 0544.05057)]. The main purpose of the paper under review is to generalize this result. The authors call a set \(\{u_i,v_i\}_{i=1}^k\) of distinct vertices of \(Q_n\) connectable if there exists a path between \(u_i\) and \(v_i\) for all \(i\in\{1,2,\dots,k\}\) such that each vertex of \(Q_n\) lies on exactly one of these paths. It is easy to see that a~connectable set is necessarily balanced in the sense that it contains the same number of vertices from both partite classes of \(Q_n\). The main result of this paper says that there exists a function \(\pi_1\) such that balance is also sufficient to guarantee connectability if and only if \(n\geq\pi_1(k)\). In particular, considering only the case when the distance of \(u_i\) and \(v_i\) is odd for all \(i\in\{1,2,\dots,k\}\), there exists a function \(\pi_2\) such that each such set \(\{u_i,v_i\}_{i=1}^k\) in \(Q_n\) is connectable if and only if \(n\geq\pi_2(k)\). The proofs, based on an inductive construction of the desired paths, also provide loose upper bounds on \(\pi_1\) and \(\pi_2\) and exact values for \(k\leq3\). The determination of the other exact values of both functions is left as an open problem.