Single-source three-disjoint path covers in cubes of connected graphs

• To establish the exact condition for the cube of a connected graph to have a 3-DPC joining a single source to three sinks (Theorem 1).
• To show that the cube of a connected graph always has a 3-DPC joining arbitrary two vertices (Theorem 2).
• To provide constructive proofs for the above two problems so that the respective 3-DPC finding algorithms may easily be constructed.

A k-disjoint path cover (k-DPC for short) of a graph is a set of k internally vertex-disjoint paths from given sources to sinks that collectively cover every vertex in the graph. In this paper, we establish a necessary and sufficient condition for the cube of a connected graph to have a 3-DPC joining a single source to three sinks. We also show that the cube of a connected graph always has a 3-DPC joining arbitrary two vertices.