修正泡型图的条件匹配排除  

Conditional matching preclusion of the modified bubble sort graph

作　　者：王世英[1] 杨婕 马晓蕾 Wang Shiying;Yang Jie;Ma Xiaolei(College of Mathematics and Information Science,Henan Normal University,Xinxiang 453007,China)

机构地区：[1]河南师范大学数学和信息科学学院,河南新乡453007

出　　处：《河南师范大学学报（自然科学版）》2021年第1期1-9,F0002,共10页Journal of Henan Normal University(Natural Science Edition)

基　　金：国家自然科学基金(61772010)。

摘　　要：一个图G的条件匹配排除数是最少的边的数量,使得删去这些边后形成的图既没有孤立点也没有完美匹配和几乎完美匹配.任何一个这样的边集称为G的一个最优条件匹配排除集.条件匹配排除数是衡量网络在边故障情况下的鲁棒性的参数之一.主要给出了修正泡型图的条件匹配排除数是2n-2(n≥5).The conditional matching preclusion number of a graph is the minimum number of edges,whose deletion results in a graph with no isolated vertices that has neither perfect matchings nor almost-perfect matchings.Any such optimal set is called an optimally conditional matching preclusion set.The conditional matching preclusion number is one of the parameters to measure the robustness of interconnection networks in the event of edge failure.In this paper,we work out that the conditional matching preclusion number of the modified bubble sort graph is 2n-2(n≥5).

关 键 词：CAYLEY图 修正泡型图 匹配 条件匹配排除 

分 类 号：O157.5[理学—基础数学]