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

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

作　　者：姚菊田 

机构地区：[1]绍兴文理学院数理信息学院,浙江 绍兴

出　　处：《应用数学进展》2024年第2期606-611,共6页Advances in Applied Mathematics

摘　　要：一个二部图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补,本文得到一种半正则二部图的补图的生成树计数一般公式,并得到一些特殊半正则二部图补图的生成树数目计数公式。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 = (V1, V2, E) be a connected bipartite graph with bipartition(V1, V2). V1 ∪ V2 = V (G) and V1 ∩ V2 = ∅. If G satisfies |V1| = s, |V2| = t, and ∀ui ∈ V1, dG(ui) =x (i = 1, . . . , s), ∀vj ∈ V2, dG(vj ) = 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 expressionfor 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.

关 键 词：二部图 半正则 Kirchhoff矩阵-树定理 SCHUR补 

分 类 号：O15[理学—数学]