Strong matching preclusion
Strong matching preclusion
复制标题
DOI：
10.1016/j.tcs.2011.08.008
复制
发表时间：
2011-10
期刊：
影响因子：
--
通讯作者：
Jung-Heum Park;I. Ihm
中科院分区：
文献类型：
--
作者：
Jung-Heum Park;I. Ihm
匹配排除问题，介绍了布里格姆等人。[R.C. Brigham，F. Harary，E.C. Violin和J. Yellen，Perfect-matching preclusion，Congressus Numerantium 174（2005）185-192]研究了如何通过删除尽可能少的边来有效地使图既没有完美匹配也没有几乎完美匹配。扩展这个概念，我们考虑一个更一般的匹配排除问题，称为强匹配排除，其中删除顶点是额外允许的。我们建立了各类图的强匹配排除数和所有可能的最小强匹配排除集。
The matching preclusion problem, introduced by Brigham et al. [R.C. Brigham, F. Harary, E.C. Violin, and J. Yellen, Perfect-matching preclusion, Congressus Numerantium 174 (2005) 185–192], studies how to effectively make a graph have neither perfect matchings nor almost perfect matchings by deleting as small a number of edges as possible. Extending this concept, we consider a more general matching preclusion problem, called the strong matching preclusion, in which deletion of vertices is additionally permitted. We establish the strong matching preclusion number and all possible minimum strong matching preclusion sets for various classes of graphs.