Matching preclusion and conditional matching preclusion problems for tori and related Cartesian products
Matching preclusion and conditional matching preclusion problems for tori and related Cartesian products
复制标题
DOI：
10.1016/j.dam.2012.03.014
复制
发表时间：
2012-08
期刊：
影响因子：
--
通讯作者：
E. Cheng;László Lipták
中科院分区：
文献类型：
--
作者：
E. Cheng;László Lipták
偶图的匹配排除数是指删除该偶图的边而使该偶图不存在完美匹配的最小边数。对于许多互连网络，最优集恰好是由单个顶点诱导的集。引入偶图的条件匹配排除数来寻找单点诱导的障碍集以外的障碍集。它被定义为删除导致图没有孤立点和没有完美匹配的边的最小数量。本文通过证明包含圈的图的笛卡尔积的匹配排除和条件匹配排除结果，研究了环面图的匹配排除问题。我们的结果推广了Wang等人给出的k元n-立方体的结果。（2010）[10]，并为这些图的最佳条件匹配排除集提供分类。
The matching preclusion number of an even graph is the minimum number of edges whose deletion results in a graph that has no perfect matchings. For many interconnection networks, the optimal sets are precisely those induced by a single vertex. The conditional matching preclusion number of an even graph was introduced to look for obstruction sets beyond those induced by a single vertex. It is defined to be the minimum number of edges whose deletion results in a graph with no isolated vertices and no perfect matchings. In this paper we study this problem for the tori by proving matching preclusion and conditional matching preclusion results of the Cartesian products of graphs involving cycles. Our results generalize the one given for k-ary n-cube by Wang et al. (2010) [10] as well as provide classification for optimal conditional matching preclusion sets for these graphs.