关键词: 最大匹配, 新的最大匹配图, 因子临界图, 有正赢量的二部图

Abstract: The new maximum matching graph $\mathcal{NM}(G)$ of a graph $G$ is a graph where vertices are maximum matchings of $G$ and two maximum matchings $M_{1}$ and $M_{2}$ are adjacent in $\mathcal{NM}(G)$ if the symmetric difference of $M_{1}$ and $M_{2}$ induces a path (there is no limit for the length of the path). In the paper, we study the connection of new maximum matching graph, and the necessary and sufficient condition of the new maximum matching graph being a complete graph or a tree or a cycle are obtained, respectively.

Key words: maximum matching, new maximum matching graph, factor-critical graph, bipartite graph with positive surplus