On the enumeration of colored spanning trees in a graph.

摘要

This dissertation focuses on different generalizations of the Matrix Tree Theorem. Theory and algorithms for determining all spanning trees of a certain color type in an arbitrary graph with colored edges are presented. A generating function for all colored spanning trees containing a given tree is presented as well. These results are extended to colored spanning forests. The algorithm is used to exhaustively enumerate isomorphic colored tree partitions for K₆ and K₈ when the latter are colored by matchings. This answers part of a conjecture of Richard Brualdi (1996).