论文标题
与对成对的不相交匹配有关的饱和图的表征
Characterization of saturated graphs related to pairs of disjoint matchings
论文作者
论文摘要
我们以有限图的比率研究了最大匹配中最大匹配的大小，最大边缘总数和最大的匹配。以前，该比率在4/5到1之间，并且完全表征了达到4/5的图形。在本文中，我们首先表明图形分解为路径，甚至循环都提供了一种研究该比率的新方法。然后，我们使用此技术来表征所有图表1在所有图表中达到比率1的表征，这些图可以通过一定选择的最大匹配和最大差异匹配来覆盖。
We study the ratio, in a finite graph, of the sizes of the largest matching in any pair of disjoint matchings with the maximum total number of edges and the largest possible matching. Previously, it was shown that this ratio is between 4/5 and 1, and the class of graphs achieving 4/5 was completely characterized. In this paper, we first show that graph decompositions into paths and even cycles provide a new way to study this ratio. We then use this technique to characterize the graphs achieving ratio 1 among all graphs that can be covered by a certain choice of a maximum matching and maximum disjoint matchings.
