Back to Search Start Over

Counting spanning trees in a complete bipartite graph which contain a given spanning forest

Authors :
Dong, Fengming
Ge, Jun
Source :
Journal of Graph Theory (2022)
Publication Year :
2021

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 $(X,Y)$ be the bipartition of the complete bipartite graph $K_{m,n}$ with $|X|=m$ and $|Y|=n$. We prove that for any given spanning forest $F$ of $K_{m,n}$ with components $T_1,T_2,\ldots,T_k$, the number of spanning trees in $K_{m,n}$ which contain all edges in $F$ is equal to $$ \frac 1{mn}\left(\prod_{i=1}^k (m_in+n_im)\right) \left (1-\sum_{i=1}^{k}\frac{m_in_i}{m_in+n_im}\right ), $$ where $m_i=|V(T_i)\cap X|$ and $n_i=|V(T_i)\cap Y|$ for $i=1,2,\ldots,k$.

Details

Database :
arXiv
Journal :
Journal of Graph Theory (2022)
Publication Type :
Report
Accession number :
edsarx.2103.05294
Document Type :
Working Paper
Full Text :
https://doi.org/10.1002/jgt.22812