THE COLOR-DEGREE MATRIX AND THE NUMBER OF MULTICOLORED TREES IN STAR DECOMPOSITIONS

In a previous paper we investigated the problem of counting the number of multicolored spanning trees in biclique decompositions. In particu lar for acyclic decompositions we found the minimum and maximum number s of multicolored trees. We now introduce the color-degree matrix C an d show that the number of multicolored trees is bounded below by the d eterminant of C with a row deleted. In fact, we obtain equality for ac yclic decompositions and for star decompositions. Unfortunately, for a rbitrary decompositions the ratio of this determinant to the actual nu mber of trees can approach zero. We find that star decompositions on n vertices are in one to one correspondence with tournaments on n - 1 v ertices. This allows us to determine that the minimum number of multic olored trees among all star decompositions of K(n) is (n - 1 )! and th e average number is ((n + 1)/2)n-2. We bound the maximum number of mul ticolored trees between this average and right perpendicular n2/4 left perpendicular((n-1)/2) - right perpendicular (n - 2)(2)/4 left perpen dicular((n - 1)/2). (C) 1994 Academic Press, Inc.