Spanning trees in complete bipartite graphs and resistance distance in nearly complete bipartite graphs

Using the theory of electrical network, we first obtain simple formulas for the number of spanning trees of a complete bipartite graph containing a certain matching or a certain tree. Then we compute the effective resistances (i.e., resistance distance in graphs) in the nearly complete bipartite graph G(m, n, p) = K-m,K-n - pK(2) (p <= min{m, n}), which extends a recent result (Ye and Yan, 2019) on the effective resistances in G(n, n, p). As a corollary, we obtain the Kirchhoff index of G(m, n, p) which extends a previous result by Shi and Chen. Using the effective resistances in G(m, n, p), we find a formula for the number of spanning trees of G(m, n, p). In the end, we prove a general result for the number of spanning trees of a complete bipartite graph containing several edges in a certain matching and avoiding others. (C) 2020 Elsevier B.V. All rights reserved.