Counting Isomorphism Classes of Spanning Trees of Complete Bipartite Graphs

Abstract

Spanning trees of complete bipartite graphs exhibit a rich interaction between degree sequences and graph structure. In this paper, we obtain lower bounds on the number of isomorphism classes of spanning trees in $K_{a,b},2\le a\le b$ in terms of $P_a(a+b-1)$ and $P_b(a+b-1)$ where $P_k(m)$ is the number of integer partitions of $m$ of length $k$. Furthermore, we obtain an upper bound in terms of $a$ and $b$.

arXiv comment5 pages, 3 figures