Multicolored trees in complete graphs

A multicolored tree is a tree whose edges have different colors. Brualdi and Hollingsworth [5] proved in any proper edge coloring of the complete graph K-2n(n > 2) with 2n - 1 colors, there are two edge-disjoint multicolored spanning trees. In this paper we generalize this result showing that if (a(1) ,..., a(k)) is a color distribution for the complete graph K-n, n >= 5, such that 2 <= a(1) <= a(2) <= (...) <= a(k) <= (n + 1)/2, then there exist two edge-disjoint multicolored spanning trees. Moreover, we prove that for any edge coloring of the complete graph K, with the above distribution if T is a non-star multicolored spanning tree of Kn, then there exists a multicolored spanning tree T' of K-n such that T and T' are edge-disjoint. Also it is shown that if K-n, n >= 6, is edge colored with k colors and k >= ((n-2)(2)) + 3, then there exist two edge-disjoint multicolored spanning trees. (c) 2006 Wiley Periodicals, Inc.