Counting spanning trees in a complete bipartite graph which contain a given spanning forest
Fengming Dong, Jun Ge
Abstract
Abstract In this article, we extend Moon's classic formula for counting spanning trees in complete graphs containing a fixed spanning forest to complete bipartite graphs. Let be the bipartition of the complete bipartite graph with and . We prove that for any given spanning forest of with components , the number of spanning trees in which contain all edges in is equal to where and for .
Topics & Concepts
Spanning treeCombinatoricsBipartite graphMathematicsTrémaux treeComplete bipartite graphMinimum spanning treeMinimum degree spanning treeDiscrete mathematicsArboricityGraphLine graphPlanar graphPathwidthGraph theory and applicationsLimits and Structures in Graph TheoryAdvanced Graph Theory Research