The Isomorphic Factorization of Complete Bipartite Graphs into Trees

Abstract

We study the isomorphic factorization of complete bipartite graphs into trees. It is known that for complete bipartite graphs, the divisibility condition is also a sufficient condition for the existence of isomorphic factorization. We give necessary and sufficient conditions for the divisibility, that is, necessary and sufficient conditions for a pair $[m,n]$ such that $mn$ is divisible by $(m+n-1)$, and investigate structures of the set of pairs $[m,n]$ satisfying divisibility. Then we prove that the divisibility condition is also sufficient for the existence of an isomorphic tree factor of a complete bipartite graph by constructing the tree dividing $K(m,n)$.