Graphs in which some and every maximum matching is uniquely restricted
Graphs in which some and every maximum matching is uniquely restricted
复制标题
某些和每个最大匹配都受到唯一限制的图
DOI：
10.1002/jgt.22239
复制
发表时间：
2015
影响因子：
0.9
通讯作者：
U. Souza
中科院分区：
文献类型：
--
作者：
L. Penso;D. Rautenbach;U. Souza
图G中的匹配M是唯一限制的，如果G中不存在与M不同但覆盖与M相同顶点的匹配M′。解决了Golumbic，Hirst和Lewenstein提出的一个问题，我们刻画了一些最大匹配是唯一限制的图。解决了Levit和Mandrescu提出的一个问题，我们刻画了每个最大匹配唯一受限的图。我们的两个特征导致有效的识别算法相应的图。
A matching M in a graph G is uniquely restricted if there is no matching M′ in G that is distinct from M but covers the same vertices as M. Solving a problem posed by Golumbic, Hirst, and Lewenstein, we characterize the graphs in which some maximum matching is uniquely restricted. Solving a problem posed by Levit and Mandrescu, we characterize the graphs in which every maximum matching is uniquely restricted. Both our characterizations lead to efficient recognition algorithms for the corresponding graphs.