The Color-Degree Matrix and the Number of Multicolored Trees in Star Decompositions

✍ Scribed by J.Q. Liu; A.J. Schwenk

• Publisher: Elsevier Science
• Year: 1994
• Tongue: English
• Weight: 473 KB
• Volume: 60
• Category: Article
• ISSN: 0095-8956
• DOI: 10.1006/jctb.1994.1014

✦ Synopsis

In a previous paper we investigated the problem of counting the number of multicolored spanning trees in biclique decompositions. In particular, for acyclic decompositions we found the minimum and maximum numbers of multicolored trees. We now introduce the color-degree matrix (C) and show that the number of multicolored trees is bounded below by the determinant of (C) with a row deleted. In fact, we obtain equality for acyclic decompositions and for star decompositions. Unfortunately, for arbitrary decompositions the ratio of this determinant to the actual number of trees can approach zero. We find that star decompositions on (n) vertices are in one to one correspondence with tournaments on (n-1) vertices. This allows us to determine that the minimum number of multicolored trees among all star decompositions of (K_{n}) is ((n-1)) ! and the average number is (((n+1) / 2)^{n-2}). We bound the maximum number of multicolored trees between this average and (\left\lfloor n^{2} / 4\right\rfloor^{(n-1,2}-\left\lfloor(n-2)^{2} / 4\right\rfloor^{(n-1) 2}). ' 1994 Academic Press. Inc.