广义Petersen图的匹配排除问题

发布时间：2018-08-02 20:25

【摘要】：在互连网络中,匹配排除用于衡量在边连接失败的情形下互连网络的强健性.一个偶阶图的匹配排除数是指最少边数,使得删除这些边所得图不存在完美匹配.很多互连网络被证明是极大匹配的和超匹配的.最近,条件匹配排除数的概念被引入来研究不是关联同一个顶点的匹配排除集.一个偶阶图的条件匹配排除数是指最少边数,使得删除这些边所得图不存在完美匹配也不存在孤立点.本文主要研究了广义Petersen图(9),6))的匹配排除和条件匹配排除问题.我们得到广义Petersen图(9),6))是极大匹配的;广义Petersen图(9),6))除了少数几种情况都是超匹配的,条件极大匹配的.此外,我们表明(9),6))不是条件超匹配的,如果它包含3长圈或4长圈或5长圈.由此可知(9),1)和(9),2)不是条件超匹配的,而且我们也确定了(9),1)和(9),2)的全部非平凡的最优条件匹配排除集.
[Abstract]:In interconnection networks, matching exclusion is used to measure the robustness of the interconnection network in the event of a failure of an edge connection. The matching exclusion number of a graph of even order refers to the minimum number of edges so that there is no perfect match between the graphs obtained by deleting these edges. Many interconnection networks have been proved to be extremely matched and supermatched. Recently, the concept of conditional matching exclusion number was introduced to study the matching exclusion set which is not associated with the same vertex. The conditional matching exclusion number of a graph of even order refers to the minimum number of edges so that there is no perfect matching and no outliers in the graph obtained by deleting these edges. In this paper, the problem of matching exclusion and conditional matching exclusion of generalized Petersen graph (9) is studied. We obtain that the generalized Petersen graph (9) ~ (6) is maximal matched, and the generalized Petersen graph (9) ~ (6) is supermatched except for a few cases. In addition, we show that (9) (6) is not conditional supermatch if it contains 3 long cycles, 4 long cycles or 5 long cycles. It can be seen that (9) 1) and (9) 2) are not conditional supermatched, and we also determine all the nontrivial optimal conditional matching exclusion sets of (9) 1) and (9) 2).
【学位授予单位】：兰州大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O157.5

【相似文献】