Back to Search
Start Over
Counting spanning trees in a complete bipartite graph which contain a given spanning forest
- 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$.
- Subjects :
- Mathematics - Combinatorics
05C30, 05C05
Subjects
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