A linear-time algorithm for finding a one-to-many 3-disjoint path cover in the cube of a connected graph

Abstract Given two disjoint vertex sets S = { s } and T = { t 1 , t 2 , t 3 } of a connected graph, a one-to-many 3-disjoint path cover joining S and T is a vertex-disjoint path cover { P 1 , P 2 , P 3 } such that each path P i joins s and t i . In this paper, we present an efficient algorithm that builds, if exists, a one-to-many 3-disjoint path cover in the cube of a connected graph G joining the two terminal sets. Interestingly enough, we show that a carefully selected spanning tree or spanning unicyclic subgraph of G is all we need to find the desired disjoint path cover in time linear to the size of G .