One-to-one Disjoint-path Covers of Leaf-sort Graphs

Parallel paths of interconnection networks have attracted much attention in parallel computing systems, they are studied in terms of disjoint paths in an undirected graph [Formula: see text]. A [Formula: see text]-disjoint path cover (k-DPC for short) of a graph [Formula: see text] is a set of [Formula: see text] (internally) disjoint paths that altogether cover every vertice of the graph. A bipartite graph [Formula: see text] is one-to-one bi-k-DPC if there is a k-DPC between any pair of vertices in different partite sets. A bipartite graph is hamiltonian laceable if there exists a hamiltonian path between any pair of vertices in different partite sets. The [Formula: see text]-dimensional leaf-sort graph [Formula: see text] has many good properties, including bipartite, symmetry, vertex-transitive. In this paper, we prove that [Formula: see text] has one-to-one bi-[Formula: see text]-DPC between any two vertices [Formula: see text] and [Formula: see text] in [Formula: see text], where [Formula: see text], [Formula: see text] in different partite sets, and [Formula: see text] is hamiltonian laceable.