Matching preclusion and conditional matching preclusion for bipartite interconnection networks I: Sufficient conditions
Matching preclusion and conditional matching preclusion for bipartite interconnection networks I: Sufficient conditions
复制标题
DOI：
10.1002/net.20440
复制
发表时间：
2012-07
期刊：
影响因子：
2.1
通讯作者：
E. Cheng;Philip Hu;Roger Jia;László Lipták
中科院分区：
文献类型：
--
作者：
E. Cheng;Philip Hu;Roger Jia;László Lipták
图的匹配排除数是删除导致图既没有完美匹配也没有几乎完美匹配的边的最小数量。对于许多互连网络来说，最优集正是由单个顶点导出的集。最近，引入了图的条件匹配排除数来寻找超出单个顶点引起的障碍集。该数量被定义为边的最小数量，其删除导致图没有孤立的顶点，既没有完美匹配也没有几乎完美匹配。在本文中，我们证明了有关二分图的匹配排除数和条件匹配排除数以及它们各自的最佳集的分类的一般结果。 © 2011 Wiley periodicals, Inc. 网络，2011
The matching preclusion number of a graph is the minimum number of edges whose deletion results in a graph that has neither perfect matchings nor almost‐perfect matchings. For many interconnection networks, the optimal sets are precisely those induced by a single vertex. Recently, the conditional matching preclusion number of a graph was introduced to look for obstruction sets beyond those induced by a single vertex. This number is defined to be the minimum number of edges whose deletion results in a graph with no isolated vertices that has neither perfect matchings nor almost‐perfect matchings. In this article, we prove general results regarding the matching preclusion number and the conditional matching preclusion number as well as the classification of their respective optimal sets for bipartite graphs. © 2011 Wiley Periodicals, Inc. NETWORKS, 2011