半正则二部图的补图生成树计数的一种新方法

A New Method for the Enumerattion of the Number of Spanning Trees of the Complement of a Biregular Graph

摘要: 一个二部图G = (U, V, E)是半正则当且仅当同一部顶点集的两个顶点的度相等。 进一步，设G = (V₁, V₂, E)是一个二部划分为(V₁, V₂)的连通二部图，即V₁ ∪ V₂ = V (G) 且V1 ∩ V₂ = ∅。 若G满足|V₁| = s, |V₂| = t，且∀u_i ∈ V1, d_G(u_i) = x (i = 1, . . . , s), ∀v_j ∈ V₂, d_G(v_j ) = y (j = 1, . . . , t)，则称G是一个半正则二部图，记作G = (s, t; x, y)。 利用Kirchhoff矩阵-树定理和矩阵的Schur补，本文得到一种半正则二部图的补图的生成树计数一般公式，并得到一些特殊半正则二部图补图的生成树数目计数公式。

Abstract: A biregular (semiregular bipartite) graph is defined as a bipartite graph G = (U, V, E) for which erery two vertices on the same side of the given bipartition have the same degree as each other. Let G = (V₁, V₂, E) be a connected bipartite graph with bipartition (V₁, V₂). V₁ ∪ V₂ = V (G) and V₁ ∩ V₂ = ∅. If G satisfies |V₁| = s, |V₂| = t, and ∀u_i ∈ V₁, d_G(u_i) =x (i = 1, . . . , s), ∀v_j ∈ V₂, d_G(v_j ) = y (j = 1, . . . , t), then G is a semiregular bipartite graph, denoted as G = (s, t; x, y) . Based on the classical Kirchhoff matrix-tree theorem, and by using the Schur complement of a block of block matrix, we show a general expression for the number of spanning trees of the complement of a biregular graph G is given. As applications, several formulas for the number of spanning trees of the complement of various classes of biregular graph were obtained