On tree factorizations of Kn

In this paper we exhibit a class of trees with the property that if T_k is a tree on k vertices that belongs to this class, then necessary and sufficient conditions for K_n to have a T_k-factorization are simply n = 0 (mod k) and n = 1 (mod 2(k - 1)). (This class is large and in particular contains all caterpillars with an odd number of vertices.) As a corollary we obtain necessary and sufficient conditions for the existence of a K_1,k-1-factorization of K_n, which previously had only been known to be asymptotically sufficient. © 1993 John Wiley & Sons, Inc.