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

DOI10.1002/JGT.22812MaRDI QIDQ6081889zbMATH OpenOpenAlexFDO

Authors

Publication date 5 October 2023

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2103.05294

zbMATH Keywords

complete bipartite graphmultigraphspanning treeweighted graph

Mathematics Subject Classification ID

Trees (05C05) Enumeration in graph theory (05C30)

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 ${\displaystyle }$ frac 1{mn}left(prod_{i=1}^k (m_in+n_im) ight) left (1-sum_{i=1}^{k}frac{m_in_i}{m_in+n_im} ight ), ${\displaystyle }$ where $m_i=|V(T_i)capX|$ and $n_i=|V(T_i)capY|$ for $i=1,2,ldots,k$.

Recommendations

• Enumeration of spanning trees of complete multipartite graphs containing a fixed spanning forest
• scientific article; zbMATH DE number 2192142
• Enumeration for spanning forests of complete bipartite graphs.
• Computing the number of h-edge spanning forests in complete bipartite graphs
• Enumeration for no-trivial spanning forests of complete bipartite graphs.

Cites work

• A simple formula for the number of spanning trees of line graphs
• Express the number of spanning trees in term of degrees
• Expression for the number of spanning trees of line graphs of arbitrary connected graphs
• scientific article; zbMATH DE number 487720 (Why is no real title available?)
• On $W$-bases of directed graphs
• On the number of spanning trees of some irregular line graphs
• Spanning trees in complete bipartite graphs and resistance distance in nearly complete bipartite graphs
• The number of spanning trees of the Bruhat graph
• The second moment of the complexity of a graph

Cited in

(29)

• Counting spanning trees in almost complete multipartite graphs
• Spanning trees in complete bipartite graphs and resistance distance in nearly complete bipartite graphs
• Enumeration for no-trivial spanning forests of complete bipartite graphs.
• scientific article; zbMATH DE number 3884200 (Why is no real title available?)
• scientific article; zbMATH DE number 1778429 (Why is no real title available?)
• Computing the number of h-edge spanning forests in complete bipartite graphs
• Counting degree sequences of spanning trees in bipartite graphs: A graph‐theoretic proof
• scientific article; zbMATH DE number 2192142 (Why is no real title available?)
• Enumeration for spanning forests of complete bipartite graphs.
• Enumeration of spanning trees of complete multipartite graphs containing a fixed spanning forest
• scientific article; zbMATH DE number 7771742 (Why is no real title available?)
• Enumeration of spanning trees containing perfect matchings in hexagonal chains with a unique kink
• Enumeration of spanning trees with a perfect matching of hexagonal lattices on the cylinder and Möbius strip
• The number of spanning trees in K_n-complement of a bipartite graph
• Resistance distances and the Moon-type formula of a vertex-weighted complete split graph
• Counting spanning trees of multiple complete split-like graph containing a given spanning forest
• Around the number of trees in distance-hereditary graphs
• Counting spanning trees with one perfect matching in helicene polygonal chains on the plane and cylinder
• The number of odd spanning trees in the complete graphs
• Resistance distance and spanning trees of generalized multiple complete split-like graph
• On a conjecture regarding spanning tree edge dependences of planar graphs
• The number of spanning trees of the bipartite complement of a semiregular bipartite graph
• Weighted Moon-type formulae for complete graphs and complete bipartite graphs
• Calculating the entropy and number of spanning trees of a complex network model
• A variant of the Teufl-Wagner formula and applications
• The number of spanning trees in \(K_{m , n}\)-complements of bipartite graphs
• On saturated non-covered graphs
• Counting matchable spanning trees of join graphs
• The bipartite analogue of a classical spanning tree enumeration formula, Boolean functions, and their applications to counting odd spanning trees

This page was built for publication: Counting spanning trees in a complete bipartite graph which contain a given spanning forest

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6081889)