On tree factorizations of K n

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.