论文标题
最大化图形完美匹配的最小值和最大强迫数量
Maximizing the Minimum and Maximum Forcing Numbers of Perfect Matchings of Graphs
论文作者
论文摘要
让$ g $是一个简单的图表，具有$ 2N $的顶点和完美的匹配。完美匹配的$ m $ $ g $的强迫数量$ f（g，m）是$ m $的最小的$ m $的基数，其中包含在其他没有其他完美匹配的$ g $中。在所有完美匹配$ m $ g $中，最低和最大值$ f（g，m）$称为$ g $的最小和最大强迫数量，分别用$ f（g）$和$ f（g）$表示。然后$ f（g）\ leq f（g）\ leq n-1 $。 Che and Chen（2011）提出了一个开放问题：如何用$ f（g）= n-1 $来表征图形$ g $。后来他们表明，对于双分图$ g $，$ f（g）= n-1 $，并且仅当$ g $是完整的两部分图$ k_ {n，n，n} $。在本文中，我们完全解决了CHE和Chen的问题，并证明$ f（g）= n-1 $，并且仅当$ g $是完整的多方图或从完整的两部分图获得的图形$ k_ {n，n} $通过在同一partite集中添加任意边缘来获得的图。对于所有图形$ g $，$ f（g）= n-1 $，我们证明，每个这样的图$ g $的强迫频谱通过匹配2个开关和所有此类图的最小强迫数量$ g $形成整数间隔，从而形成了$ \ lfloor \ lfloor \ frac \ frac {n} n} {2} {2} $ n $ n $ n $ n $ n $ n $ n。
Let $G$ be a simple graph with $2n$ vertices and a perfect matching. The forcing number $f(G,M)$ of a perfect matching $M$ of $G$ is the smallest cardinality of a subset of $M$ that is contained in no other perfect matching of $G$. Among all perfect matchings $M$ of $G$, the minimum and maximum values of $f(G,M)$ are called the minimum and maximum forcing numbers of $G$, denoted by $f(G)$ and $F(G)$, respectively. Then $f(G)\leq F(G)\leq n-1$. Che and Chen (2011) proposed an open problem: how to characterize the graphs $G$ with $f(G)=n-1$. Later they showed that for a bipartite graph $G$, $f(G)=n-1$ if and only if $G$ is a complete bipartite graph $K_{n,n}$. In this paper, we completely solve the problem of Che and Chen, and show that $f(G)=n-1$ if and only if $G$ is a complete multipartite graph or a graph obtained from complete bipartite graph $K_{n,n}$ by adding arbitrary edges in the same partite set. For all graphs $G$ with $F(G)=n-1$, we prove that the forcing spectrum of each such graph $G$ forms an integer interval by matching 2-switches and the minimum forcing numbers of all such graphs $G$ form an integer interval from $\lfloor\frac{n}{2}\rfloor$ to $n-1$.
