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

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