诱导匹配、有序匹配与二分图的Castelnuovo-Mumford正则性

Induced matching, ordered matching and Castelnuovo-Mumford regularity of bipartite graphs

摘要 Abstract

设G为有限简单图,分别用indm(G)和ordm(G)表示G的诱导匹配数和有序匹配数。我们刻画了所有满足indm(G) = ordm(G)的二分图G。对于这类图,我们建立了边理想的幂次的Castelnuovo-Mumford正则性和覆盖理想的幂次的深度。此外,我们给出了完全二分图K_{m,n}的连通非同构生成子图数量的公式,其中满足indm(G) = ordm(G) = 2的情况,并在m = 2,3,4且m ≤ n时给出显式表达式。

Let G be a finite simple graph and let indm(G) and ordm(G) denote the induced matching number and the ordered matching number of G, respectively. We characterize all bipartite graphs G with indm(G) = ordm(G). We establish the Castelnuovo-Mumford regularity of powers of edge ideals and depth of powers of cover ideals for such graphs. We also give formulas for the count of connected non-isomorphic spanning subgraphs of the complete bipartite graph K_{m,n} for which indm(G) = ordm(G) = 2, with an explicit expression for the count when m = 2,3,4 and m <= n.