Congressus Numerantium, Vol. 100 (1994), pp. 225-243.
Ömer Egecioglu and Jeffrey B. Remmel
A Bijection for Spanning Trees of Complete Multipartite Graphs
Abstract.
We construct a bijective proof for the number of spanning trees of complete
multipartite graphs. The weight preserving properties of our bijection yields a
6-variate weight generating function which keeps track of various statistics on
spanning trees. This bijection allows for the ranking and unranking of the
spanning trees of an n-vertex complete multipartite graph in O(n) time.
As a further application, we compute the asymptotic distribution of leaves in
these families of spanning trees.
omer@cs.ucsb.edu