The graphs with maximum induced matching and maximum matching the same size
The graphs with maximum induced matching and maximum matching the same size
复制标题
具有最大诱导匹配和最大匹配相同大小的图
DOI：
10.1016/j.disc.2004.07.022
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
Tracy Walker
中科院分区：
文献类型：
--
作者：
K. Cameron;Tracy Walker
Kobler和Rotics给出了一个polytime算法，用于判定一个图是否具有相同大小的最大诱导匹配和最大匹配，以及在等式成立的图中找到最大诱导匹配。我们给出了这些图的一个简单的特征。我们的表征提供了一个更简单的识别算法。
Kobler and Rotics gave a polytime algorithm for deciding if a graph has maximum induced matching and maximum matching the same size, and for finding a maximum induced matching in a graph where equality holds. We give a simple characterization of these graphs. Our characterization provides a simpler recognition algorithm.