The number of spanning trees of the bipartite complement of a semiregular bipartite graph

Abstract

For a bipartite graph $G$ on parts of cardinality $m$ and $n$, the bipartite complement of $G$ is defined as the graph obtained from the complete bipartite graph $K_{m,n}$ by removing the edges of an isomorph of $G$. In this paper, based on the matrix-tree theorem and the Schur complement technique, we give a determinant expression for the number of spanning trees of the bipartite complement of a semiregular bipartite graph. As by-products, we show that the corresponding result can generalize some previous results on the problem of enumerating spanning trees and obtain an explicit formula for the number of spanning trees of the bipartite complement of the subdivison of a regular circulant graph.