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 G. A k -disjoint path cover (k-DPC for short) of a graph G is a set of k (internally) disjoint paths that altogether cover every vertice of the graph. A bipartite graph H 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 n -dimensional leaf-sort graph C F n has many good properties, including bipartite, symmetry, vertex-transitive. In this paper, we prove that C F n has one-to-one bi- (⌈ 3 n 2 ⌉ − 2) -DPC between any two vertices x and y in C F n , where x , y in different partite sets, and C F n is hamiltonian laceable. [ABSTRACT FROM AUTHOR]