图的最大匹配个数的下界

(厦门理工学院应用数学学院,福建 厦门 361024)

最大匹配; 因子临界图; Gallai-Edmonds结构定理

The Lower Bound on the Number of Maximum Matchings of a Graph
ZHAI Shaohui*,GUO Litao,ZHENG Yirong,ZHUANG Wei

(School of Applied Mathematics,Xiamen University of Technlogy,Xiamen 361024,China)

maximum matching; factor-critical graphs; Gallai-Edmonds structure theorem

DOI: 10.6043/j.issn.0438-0479.201712025

备注

设G是一个具有n个顶点且最大匹配为k-匹配的连通图,这里n≥2k+1.证明了G至少有n-2k+1个互不相同的最大匹配,并且刻画了恰好具有n-2k+1个最大匹配的图.

Let G be a connected graph of order n and let k be the size of maximum matchings in G,where n≥2k+1.In this paper,we present that G contains at least n-2k+1 distinct maximum matchings.In addition,we characterize graphs that possess exactly n-2k+1 distinct maximum matchings.